20120929, 08:49  #1 
Sep 2006
The Netherlands
313_{16} Posts 
Polynomial algorithm
we assume now a composite number n has at least 2 factors p and q.
We take a small random number and assume now this doesn't divide n. I take the number 3 simply for Mersenne's. Now we should in most cases be able to factorize any mersenne (didn't try yet on any number). If p divides n, then we calculate for a = 3 the fermat sequence: a^n == x Now we can calculate p, the smallest factor of n by doing: p = GCD( x  a, n ) = GCD( x  3 , n ) Example calculation by hand for the number 2047 the fermat sequence by hand: bitnr x^2 x^2 * (result1) (edit) 1 3 3 2 9 27 3 81 140 4 420 1484 5 358 1099 6 1250 213 7 639 1005 8 968 515 9 1545 1439 10 223 1565 11 601 992 Now if our number n were a prime number then 992 mod 2047 = 3 It isn't prime. So our result 992 basically divides p after we subtract 3. GCD (989 , 2047 ) = 23 Vincent Diepeveen Last fiddled with by diep on 20120929 at 09:08 
20120929, 09:01  #2  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
11585_{10} Posts 
Quote:
How does it differ from Pollard rho? 

20120929, 09:17  #3  
Sep 2006
The Netherlands
787 Posts 
Quote:
I will try write program after breakfast/lunch to factorize more Mersennes and see whether i was lucky. Last fiddled with by diep on 20120929 at 09:18 

20120929, 09:22  #4 
Romulan Interpreter
"name field"
Jun 2011
Thailand
2·47·109 Posts 
How about you try it for 29?

20120929, 10:09  #5 
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
2D41_{16} Posts 

20120929, 11:05  #6 
Sep 2006
The Netherlands
787 Posts 
I do single GCD.
I tested it. Seems not working for 29. Code:
#include <stdio.h> #define uint64 unsigned long long uint64 gcd(uint64 a,uint64 b) { printf("a = %llu b=%llu\n",a,b); if( b == 0ULL ) return a; else if( a >= b ) return gcd(b, (a % b)); else return gcd(a, (b % a)); } int main(void) { unsigned int i,p=29; uint64 m = 536870911ULL,x2=3ULL,x2y1=3ULL,g; // slow fermat printf("1 3 3\n"); for( i = 2; i <= p; i++ ) { x2 *= x2; x2 %= m; x2y1 *= x2; // mersenne has bit set everywhere x2y1 %= m; printf("%u %llu %llu\n",i,x2,x2y1); } // GCD g = gcd(x2y13ULL,m); printf("g = %llu\n",g); return 0; } Idea is: mersenne n = 2^b  1 if we do normal 3^n == x (mod n) Then we have remainder x. n is in fact 2 prime numbers p and q (in case of 2047, we skip case n has more than 2 factors for now) as n is multiple of p, we can see x as a number of times: 3^p So: 3^p * 3^q (mod n) as n is a lot larger than p, we still need to take x modulo p to get 3. In short p might divide x3. So does n, so we take then GCD(x3,n) and pray for luck. Well i guess it was worth a shot... Will test some with 2 primes p and q giving p*q = n, n not being mersenne. Last fiddled with by diep on 20120929 at 11:22 
20120929, 11:42  #7 
Jun 2003
1533_{16} Posts 
Note that GCD(a^na, n)= GCD(a(a^(n1)1), n) = GCD(a^(n1)1, n) [since a doesn't divide n]. Therefore it is effectively a p1 (rather than rho) with the exponent (n1). In the example case, we lucked out since p1 (22) divides n1 (2046). In general, this won't work.

20120929, 12:09  #8  
Sep 2006
The Netherlands
787 Posts 
Quote:
For every divisor p(i) from n: We calculate x(i) = 3^p(i) (mod n) If multiplication for all x(i) < n then this algorithms works. So the luck factor we need for algorithm to work is that multiplication remnants < n With less divisors odds is larger and when our n gets larger of course luck chance decreases. Last fiddled with by diep on 20120929 at 12:12 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Polynomial Discriminant is n^k for an n1 degree polynomial  carpetpool  Miscellaneous Math  14  20170218 19:46 
TF algorithm(s)  davieddy  Miscellaneous Math  61  20110706 20:13 
Polynomial  R.D. Silverman  NFSNET Discussion  13  20050916 20:07 
aks algorithm and polynomial  jocelynl  Math  1  20040211 05:20 
AKS  A polynomialtime algorithm for testing primality.  Maybeso  Math  11  20021120 23:39 