 mersenneforum.org Polynomial algorithm
 Register FAQ Search Today's Posts Mark Forums Read 2012-09-29, 08:49 #1 diep   Sep 2006 The Netherlands 5·157 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 * (result-1) (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 2012-09-29 at 09:08   2012-09-29, 09:01   #2
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

2C6916 Posts Quote:
 Originally Posted by diep 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 bitnr x^2 y * (y-1) 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
How many iterations does this algorithm take in the average case? In the worst case?

How does it differ from Pollard rho?   2012-09-29, 09:17   #3
diep

Sep 2006
The Netherlands

14218 Posts Quote:
 Originally Posted by xilman How many iterations does this algorithm take in the average case? In the worst case? How does it differ from Pollard rho?
It is different.

I will try write program after breakfast/lunch to factorize more Mersennes and see whether i was lucky.

Last fiddled with by diep on 2012-09-29 at 09:18   2012-09-29, 09:22 #4 LaurV Romulan Interpreter   "name field" Jun 2011 Thailand 9,973 Posts How about you try it for 29?   2012-09-29, 10:09   #5
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

11,369 Posts Quote:
 Originally Posted by diep It is different.
I asked how does it differ from Pollard rho?   2012-09-29, 11:05   #6
diep

Sep 2006
The Netherlands

14218 Posts Quote:
 Originally Posted by xilman I asked how does it differ from Pollard rho?
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(x2y1-3ULL,m);

printf("g = %llu\n",g);

return 0;
}
Will test some more.

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 x-3.
So does n, so we take then GCD(x-3,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 2012-09-29 at 11:22   2012-09-29, 11:42   #7
axn

Jun 2003

33×199 Posts Quote:
 Originally Posted by xilman I asked how does it differ from Pollard rho?
Note that GCD(a^n-a, n)= GCD(a(a^(n-1)-1), n) = GCD(a^(n-1)-1, n) [since a doesn't divide n]. Therefore it is effectively a p-1 (rather than rho) with the exponent (n-1). In the example case, we lucked out since p-1 (22) divides n-1 (2046). In general, this won't work.   2012-09-29, 12:09   #8
diep

Sep 2006
The Netherlands

5×157 Posts Quote:
 Originally Posted by axn Note that GCD(a^n-a, n)= GCD(a(a^(n-1)-1), n) = GCD(a^(n-1)-1, n) [since a doesn't divide n]. Therefore it is effectively a p-1 (rather than rho) with the exponent (n-1). In the example case, we lucked out since p-1 (22) divides n-1 (2046). In general, this won't work.
Suppose we have number of divisors of n.

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 2012-09-29 at 12:12  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Miscellaneous Math 14 2017-02-18 19:46 davieddy Miscellaneous Math 61 2011-07-06 20:13 R.D. Silverman NFSNET Discussion 13 2005-09-16 20:07 jocelynl Math 1 2004-02-11 05:20 Maybeso Math 11 2002-11-20 23:39

All times are UTC. The time now is 10:57.

Sun Jun 26 10:57:38 UTC 2022 up 73 days, 8:58, 1 user, load averages: 0.80, 0.94, 1.10