mersenneforum.org > Math Integer Factorization
 Register FAQ Search Today's Posts Mark Forums Read

2007-06-25, 17:30   #12
mgb

"Michael"
Aug 2006
Usually at home

10100002 Posts

Quote:
 Originally Posted by wpolly Code: 6943318=2*31*53*2113 262533040=2^4*5*7*11*17*23*109 8119594779270=2*3*5*13*17*139*937*9403 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.)

 2007-07-01, 10:28 #13 mgb   "Michael" 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.
 2007-07-03, 10:42 #14 robert44444uk     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
 2007-07-06, 15:29 #15 mgb   "Michael" 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
 2007-07-14, 13:59 #16 mgb   "Michael" 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
 2007-12-17, 10:43 #17 mgb   "Michael" 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. Algorithm. 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,...so 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

 Similar Threads Thread Thread Starter Forum Replies Last Post jwaltos Other Mathematical Topics 8 2015-05-22 12:20 bearnol2 Information & Answers 7 2010-12-09 02:50 mgb Math 36 2009-11-07 15:59 akruppa Factoring 14 2008-09-18 23:52 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