Here's something I posted in 1996 to sci.crypt.research, now with
some typos corrected.
It produced little reaction there. I'm hoping someone here can see
how to apply it to factoring, or perhaps just to the Mersenne case.
--------------- forwarded message -----------------------------
Like many others I've been trying for some time to find a fast
factoring algorithm and/or to break RSA. Not too surprisingly,
I haven't succeeded ( yet? :-).
I have, however, proved a couple of little theorems which I
haven't seen in the literature.
Can anyone:
find errors in my proofs?
tell me if they're original?
apply them to factoring?
Fermat's little theorem is that for any prime p and integer i:
i^p == i mod p
My 1st lemma generalises this to:
i^(p^n) == i mod p
The proof is by induction.
Fermat gives us the i = 1 case.
For the induction step:
i^(p^n) = i^(p*p^(n-1))
= (i^(p^(n-1)))^p
but by hypothesis
(i^(p^(n-1))) == i mod p
so
i^(p^n) == i^p mod p
== i mod p
QED
My 2nd lemma applies to a strong prime s
s = 2r + 1 r,s both prime
I'll also assume r odd, ignoring the r=2, s=5 case.
Fermat gives us:
i^s == i mod s
and for non-zero i:
i^(s-1) == 1 mod s
i^2r == 1 mod s
but we also have
n^r == n mod r (Fermat)
n^s == n^(2r+1)
== n^3 mod r
so
n^s = n^3 + kr for some integer k
But n^s and n^3 both have the parity of n so kr must be even
So if r is odd (if s > 5), k must be even.
Which gives us:
n^s = n^3 + 2jr for some int j
or
n^s == n^3 mod 2r
whence
i^(n^s) == i^(n^3) mod s
Which is my 2nd lemma.
------------ end forwarded message --------------------------
The second lemma can be generalised to the case where s = 2r + t
with s and t prime,
i^(n^s) == i^(n^(t+2)) mod s
which reduces to the above if t = 1.
I thought at one point this led to factoring N = xy with x, y prime.
Very likely for some t you have:
x = 2a + t
y = 2b + t
with a and b prime, in which case i^(n^xy) simplifies nicely. Unfortunately I couldn't
find an efficient way to discover t.
Can anyone suggest a method for that, or apply the lemmas in some
other interesting way?
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
