Re: Modulus, Factoring and Compressing random data

On Jan 24, 10:09 pm, Robert Wessel <robertwess...@xxxxxxxxx> wrote:
On Tue, 24 Jan 2012 09:46:59 -0800 (PST), Ernst



<Ernst_B...@xxxxxxxxxxxxx> wrote:

Hey all..

I'm putting in hours of chair time exploring the nature of
information and my attention has turned to Modulus.

I see here, through results I wasn't expecting, that modulus is used
for factoring.  I noticed the odd ends in one or zero to the sequences
and thought hey that is cool!
Turns out this is the basis of many factoring efforts.

I'm hoping for input and conversation.  In return I will moderate my
output so that it functions in a communal setting.

I love to explore so I was looking at the sequence of reminders when
they are reused as the modulus.

So N mod M = A then N mod A = B and so on.  It ends in 1 or 0.  In
simpler terms it finds a factor or it doesn't of N

Is that the basic concept behind all the Modulus based factoring?
I see names such as Fermat and Euler plus Wikipedia has a nice page
on factoring large numbers.

So, May I ask if anyone has heard of factoring with recursive modulus
as i have stated?
It must be common knowledge I assume.

This is a clear idea of what I am asking.

I was reading about using value about half the N to start.

N = 14600207906227040223 mod 2^32 = 1233334239
N mod 1233334239 = 647107860
48743583
17046876
15135939
601545, 209958,16905, 8988, 3927, 2898,  777,  441 , 21, 0

So 3*7 are factors of N

When the sequence ends in 1,0 I believe there are no factors.

I see that searching for factors through changing the M takes a long
time.

So, I am interested in using the Modulus in creative ways and I
welcome input.  I rarely use Modulus with the "things" I do but it
looks like I'm moving that way.

There is something more obvious to this.  Can anyone see it?

Either I'm not understanding your description, or this doesn't work in
general.

Consider 4295229443 (with prime factors 65537 and 65539).  If we start
what I understand the algorithm to be with 65540 (a bit more than the
square root of the original input), it does not appear to lead to
either of the factors (it results in the sequence 65540, 3, 2, 1)


I agree that there are two possible results which I am considering as
two end states for the sequence.
I see a factor when the sequence ends with the second to last element
in that series is greater than 1. The last element is always 0 from
what I have observed.

So if it sequences to {...1,0} that seems to mean it didn't find a
factor of N for our choice of {N,M}.

What I observed is that, from the data I worked by hand, that either a
factor will show for some values of N mod M or the end of the
recursive modulus sequence will be {1,0}. The sequence of recursive
mods seems to end in either Factor,0 or 1,0

That is what I have observed so far.

Let me try another run on the above example number.
N = 14600207906227040223 M = 2^32 + 5. I have not tried that value
on that number and I just read about 2^n+1 primes

14600207906227040223 mod (2^32+5) = 1416324423
315455760, 53797503, 31482342, 14395305, 1822983, 1135905, 15498,
14637, 8610, 2583, 1722, 861, 0 .

14600207906227040223 / 861 = 16957268183771243

I picked the +5 because it is a type of prime 2^n+1 I just read about
from Wikipedia's page http://en.wikipedia.org/wiki/Euler%27s_totient_function


Here is an interesting thing If I divide by 861 all is well and the
answer is 16957268183771243 but then I cannot divide that by 21 which
is the 2^32 result "3*7" and if I try to divide that by 21 it doesn't
divide whole?

That is strange.
So 14600207906227040223 is divisible by 21, 41 and 861 (29^2) but the
dividend is not divisible by other numbers that divide our N.

Look I am sleepy at the moment and am in bed with the Laptop but I'll
work on this. It's interesting

What I see at the moment and don't understand since this can't be
factoring or can it be?
14600207906227040223 is evenly divisible by 841 but that result is not
divisible by 21 after
So N mod 21 = 0, N mod 841 = 0
This is puzzling
A = 14600207906227040223 mod 841
B = 14600207906227040223 mod 21
But A mod 21 = 1 and B mod 841 = 1

That is odd.
There has to be more than one way to factor a number. I am not up on
factoring outside of the Sieve of program I read about in Sedgewick's
book on algorithms years ago.


I appreciate the time you are spending on this.



However N / 21 is not evenly divisible

.

Relevant Pages

  • Re: Modulus, Factoring and Compressing random data
    ... information and my attention has turned to Modulus. ... Turns out this is the basis of many factoring efforts. ... I see a factor when the sequence ends with the second to last element ... Here is an interesting thing If I divide by 861 all is well and the ...
    (comp.compression)
  • Re: Modulus, Factoring and Compressing random data
    ... information and my attention has turned to Modulus. ... Turns out this is the basis of many factoring efforts. ... I see a factor when the sequence ends with the second to last element ... Here is an interesting thing If I divide by 861 all is well and the ...
    (comp.compression)
  • Re: Modulus, Factoring and Compressing random data
    ... information and my attention has turned to Modulus. ... Turns out this is the basis of many factoring efforts. ... I see a factor when the sequence ends with the second to last element ... is the 2^32 result "3*7" and if I try to divide that by 21 it doesn't ...
    (comp.compression)
  • Re: NSA enhancing Linux security?
    ... a repeating pattern later on in the sequence... ... straightforward way to prove that there is no fast way of factoring ... proof by reduction to sort -- i.e., ...
    (comp.os.linux.security)
  • Re: help differentiating abs function
    ... differentiate the 2nd term because it is really just a probability ... value i.e. the prob that the mth sequence of sis the ... the Hermitian inner product of the two vectors. ...
    (comp.dsp)