Go Back > Great Internet Mersenne Prime Search > Math

Thread Tools
Old 2007-06-25, 17:30   #12
Aug 2006
Usually at home

10100002 Posts

Originally Posted by wpolly View Post
looks like it works better on smooth P-1...
Yes, it does, but you can have 'lucky strikes' even when phi(p) and phi(q) have large odd prime divisors. I'll keep you informed if I make any progress. (btw, the ideas outlined here also seem useful for DLP, which I'm also working on.)
mgb is offline   Reply With Quote
Old 2007-07-01, 10:28   #13
Aug 2006
Usually at home

24×5 Posts

I should add that these ideas come from the following observations,

Let an = apq = (ap)q = aq (mod p), by Fermat's Little Theorem.

If an = r (mod n) = r (mod p) = aq = r (mod p). Let q = xp + y.

axp + y = (ap)x + y = ax + y(mod p). Let x + y = s and let Let an = r (mod n) [which is the same as aq = r(mod p)]

s will reduce modulo ordp(a), so it is a matter of testing gcd(|r - as|, n) for s = 1, 2, 3...

In practice a factor will be found for some si < x + y. This will happen if p - 1, and/or q - 1 has small odd divisors.

This works best when q is only slightly larger than a multiple of p, i.e. q = xp + e with e = a small integer.

In practice this will often reduce to e tests.

All of the above also applies to s mod ordq(a) so there are two chances of a factor emerging.

It is best to let a = a square because, by Euler's Criterion, the order of a square is at most (p - 1)/2 or (q - 1)/2 with respect to the orders of p and q.
mgb is offline   Reply With Quote
Old 2007-07-03, 10:42   #14
robert44444uk's Avatar
Jun 2003
Oxford, UK

23×241 Posts

I rather like this factoring method!

Maybe a coincidence:

Lowest listed a(0)+1 is a factor of p+1 for both p= 6943319 and 262533041

i.e. 81 is 0 mod 6943320
54 is 0 mod 262533042

With so little information it is hard to see patterns, this will probably prove be a red herring, but it might be worthwhile testing a(0) = some other factor of these p+1 numbers, say a(0)= 404 in the case of p=6943319 to see if it produces a fancy result.

As I said, I think this is a red herring
robert44444uk is offline   Reply With Quote
Old 2007-07-06, 15:29   #15
Aug 2006
Usually at home

1208 Posts

An interesting observation...and it may not be a red herring as anything to do with p + 1 or p - 1 tends to be linked in some way to factorization.

Last fiddled with by mgb on 2007-07-06 at 15:41
mgb is offline   Reply With Quote
Old 2007-07-14, 13:59   #16
Aug 2006
Usually at home

24×5 Posts

In the search for s, as defined, there are other values of s which can find a factor.

Let o denote the order of a modulo p.

1. as - 1 = 0 (mod p) if si = o

2. (as)2 - 1 = 0 (mod p) if si = o/2 (factor as (as + 1)(as - 1))

3. |r-1 - as| if si = s-1 = o - s

4. and finally if si = x + y

all reduced modulo o.

Factorizing these congruences where appropriate and multiplying them together we have,

M = (|r - as|)(|r-1 - as|)(as - 1)(as + 1)

Now for s = 1, 2, 3, ... try gcd(M, n). If s applies to any of these factors M will be a multiple of p.

Similar reasoning gives s values modulo ordq (a)

Last fiddled with by mgb on 2007-07-14 at 14:07
mgb is offline   Reply With Quote
Old 2007-12-17, 10:43   #17
Aug 2006
Usually at home

24·5 Posts

Just a little observation to update on the above.

If d = orda(p) we know that ad = 1 (mod p).

Therefore, (ad)k = 1k = 1 (mod p).

Consider the sequence b0 b1... so that each bi is generated

a la Pollard Rho; bi+1 = f(bi) (mod s) where s = sqrt(n).

Now consider the sequence of a's:

(a^b0) (mod n)

(a^b0)^b1 (mod n)

((a^b0)^b1)^b2 (mod n)

In other words, a^b0b1b2b3...bk (mod n)

for k = 0, 1, 2,...

Let B = b0b1b2b3...bk

Now assume d = uv so that u|bi and v|bj i < k and j < k then

u|B and v|B so B = uvt. Therefore aB = (auv)t = 1t = 1 (mod p).

My point is that if d is composite, finding u and v randomly should be easy since if we find a multiple of u or v it will not be lost in subsequent exponentiations reduced modulo n because the magnitude of t is irrelevant.

That is if for some a we get aux and further along the line we get avy we have auxvy = 1xy. All the above, as usual, applies to q as well.

If u < v then u should be found by the time v is found. If d has more than 2 factors say d = uvw u < v < w then u and v (or multiples of them ) should be found by the time w is found or shortly thereafter.


Let b0 = 2. Generate the sequence b1, b2, b3,..etc a la Rho(bi-1) and reduce each bi modulo s.

At the same time generate a0, a1, a2, that ai+1 = (ai)^bi modulo n.

Check GCD(ai - 1, n).

p 2003 q 4001. Factor: 2003 at 7 iterations.

p 4001 q 9929. Factor: 4001 at 11 iterations.

p 44543 q 22271. Factor: 22271 at 138 iterations.

p 17351 q 22079. Factor: 22079 at 50 iterations.

p 11939 q 16883. Factor: 11939 at 171 iterations.

p 16883 q 10253. Factor: 16883 at 206 iterations.

p 10253 q 14879. Factor: 14879 at 62 iterations.

p 44159 q 13763. Factor: 13763 at 837 iterations.

p 13763 q 10709. Factor: 13763 at 671 iterations.

p 13313 q 10253. Factor: 13313 at 14 iterations.

p 10007 q 24659. Factor: 10007 at 26 iterations.

Last fiddled with by mgb on 2007-12-17 at 10:46
mgb is offline   Reply With Quote

Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
Utility of integer factorization. jwaltos Other Mathematical Topics 8 2015-05-22 12:20
Integer factorization? bearnol2 Information & Answers 7 2010-12-09 02:50
Integer factorization with q < 2p mgb Math 36 2009-11-07 15:59
CADO workshop on integer factorization akruppa Factoring 14 2008-09-18 23:52
Integer Factorization 2 mgb Math 5 2007-07-23 12:55

All times are UTC. The time now is 12:30.

Mon Mar 8 12:30:43 UTC 2021 up 95 days, 8:42, 0 users, load averages: 1.99, 1.64, 1.56

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.