20070625, 17:30  #12 
"Michael"
Aug 2006
Usually at home
1010000_{2} Posts 
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.)

20070701, 10:28  #13 
"Michael"
Aug 2006
Usually at home
2^{4}×5 Posts 
I should add that these ideas come from the following observations,
Let a^{n} = a^{pq} = (a^{p})^{q} = a^{q} (mod p), by Fermat's Little Theorem. If a^{n} = r (mod n) = r (mod p) = a^{q} = r (mod p). Let q = xp + y. a^{xp + y} = (a^{p})^{x + y} = a^{x + y}(mod p). Let x + y = s and let Let a^{n} = r (mod n) [which is the same as a^{q} = r(mod p)] s will reduce modulo ord_{p}(a), so it is a matter of testing gcd(r  a^{s}, n) for s = 1, 2, 3... In practice a factor will be found for some s_{i} < 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 ord_{q}(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. 
20070703, 10:42  #14 
Jun 2003
Oxford, UK
2^{3}×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 
20070706, 15:29  #15 
"Michael"
Aug 2006
Usually at home
120_{8} 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 20070706 at 15:41 
20070714, 13:59  #16 
"Michael"
Aug 2006
Usually at home
2^{4}×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. a^{s}  1 = 0 (mod p) if s_{i} = o 2. (a^{s})^{2}  1 = 0 (mod p) if s_{i} = o/2 (factor as (a^{s} + 1)(a^{s}  1)) 3. r^{1}  a^{s} if s_{i} = s^{1} = o  s 4. and finally if s_{i} = x + y all reduced modulo o. Factorizing these congruences where appropriate and multiplying them together we have, M = (r  a^{s})(r^{1}  a^{s})(a^{s}  1)(a^{s} + 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 ord_{q} (a) Last fiddled with by mgb on 20070714 at 14:07 
20071217, 10:43  #17 
"Michael"
Aug 2006
Usually at home
2^{4}·5 Posts 
Just a little observation to update on the above.
If d = ord_{a}(p) we know that a^{d} = 1 (mod p). Therefore, (a^{d})^{k} = 1^{k} = 1 (mod p). Consider the sequence b_{0} b_{1}... so that each b_{i} is generated a la Pollard Rho; b_{i+1} = f(b_{i}) (mod s) where s = sqrt(n). Now consider the sequence of a's: (a^b_{0}) (mod n) (a^b_{0})^b_{1} (mod n) ((a^b_{0})^b_{1})^b_{2} (mod n) In other words, a^b_{0}b_{1}b_{2}b_{3}...b_{k} (mod n) for k = 0, 1, 2,... Let B = b_{0}b_{1}b_{2}b_{3}...b_{k} Now assume d = uv so that ub_{i} and vb_{j} i < k and j < k then uB and vB so B = uvt. Therefore a^{B} = (a^{uv})^{t} = 1^{t} = 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 a^{ux} and further along the line we get a^{vy} we have a^{uxvy} = 1^{xy}. 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 b_{0} = 2. Generate the sequence b_{1}, b_{2}, b_{3},..etc a la Rho(b_{i1}) and reduce each b_{i} modulo s. At the same time generate a_{0}, a_{1}, a_{2},...so that a_{i+1} = (a_{i})^b_{i} modulo n. Check GCD(a_{i}  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 20071217 at 10:46 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Utility of integer factorization.  jwaltos  Other Mathematical Topics  8  20150522 12:20 
Integer factorization?  bearnol2  Information & Answers  7  20101209 02:50 
Integer factorization with q < 2p  mgb  Math  36  20091107 15:59 
CADO workshop on integer factorization  akruppa  Factoring  14  20080918 23:52 
Integer Factorization 2  mgb  Math  5  20070723 12:55 