Recursive Modulus and Factoring method

[Ernst]

Friday, February 03 2012


Hello, my name is Ernst and I am sharing an unexpected observation I
had while designing a Hash code . I see a function that reports
factors of N. The factor can be either prime or composite. The size of
the number doesn't effect functioning but it requires time.
I was looking at using the remainder of the modulus as the next
modulus value while keeping the original number.
That means each result becomes the next value our number is mod by.
Example

N is our number. M is our modulus value.
A = N mod M
B = N mod A
C = N mod B and so on.

Eventually the remainder becomes zero and if the previous value in the
sequence was larger than 1 then that is a factor of N
Well 1 is also a factor but I digress.
Now this is a function that finds a factor in the series of results
so additional effort is needed to actually factor N.


Here is a snippit of C code to aid in explaining.

z = 4295229443u;
for(x=z-1; x > 1; x-- )
{
y = z % x; prev = y;
for(;;){ if( y>0 ){ y = z % prev; if(y>0)prev = y;} else break; }
if( y == 0 & prev > 1 ) {    printf("Factor found %lu for N of  %lu
\n",prev,x); }
}

This simply scales on the value of N to generate the initial value of
M.
However if the result is not zero then the result become the next
value of the M for this series.

I have an open question as to if this method has been written about
before.
Someone suggested Euler may have and there is always the classics who
may have notes this.

Also it was mentioned that this method has the same time constraints
as other methods that are non-quantum.
This is an example I used previously that didn't start with M= N-1 yet
it displays the idea of the recursive modulus sequence.
N = 14600207906227040223 mod 2^32 = 1233334239
N mod 1233334239 = 647107860
48743583
17046876
15135939
601545, 209958,16905, 8988, 3927, 2898,  777,  441 , 21, 0

N is evenly divisible by 21, 3 and 7

This was discussed previously there. It gets a fresh start here.
http://groups.google.com/group/comp.compression/browse_thread/thread/faa3ca03c1175487/6206b31a73a01d6e

I am hoping to find reference to who first reported this function.
Some suggested Euler others reference a classroom experience.
I'd hope I did so this is an open question that you can answer for me
if you will.

Ernst

[stan]

Ernst wrote:
> Friday, February 03 2012
>
> Hello, my name is Ernst and I am sharing an unexpected observation I
> had while designing a Hash code . I see a function that reports
> factors of N.

<snip factoring>

Does this have anything to do with compression? The cryptography guys
find this sort of thing fascinating, you might try posting where
people who are actually interested in factoring might read it. As
several have pointed out, factoring hasn't proved effective in
compression and most information guys simply spend much time keeping
up with the subject.

[Ernst]

Dear Stan,
How any information and/or Maths are used depends on the individual.
Modulus is simply an arithmetic and Recursive-Modulus is another arithmetic that seems to fit in the primitive recursive function category.

I am still interested in any prior art on Recursive Modulus if any exists. Perhaps it is known by some other name? I welcome Email on the subject