mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2012-09-29, 08:49   #1
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

31316 Posts
Default 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
diep is offline   Reply With Quote
Old 2012-09-29, 09:01   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

1158510 Posts
Default

Quote:
Originally Posted by diep View Post
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?
xilman is online now   Reply With Quote
Old 2012-09-29, 09:17   #3
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

787 Posts
Default

Quote:
Originally Posted by xilman View Post
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
diep is offline   Reply With Quote
Old 2012-09-29, 09:22   #4
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

2·47·109 Posts
Default

How about you try it for 29?
LaurV is offline   Reply With Quote
Old 2012-09-29, 10:09   #5
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

2D4116 Posts
Default

Quote:
Originally Posted by diep View Post
It is different.
I asked how does it differ from Pollard rho?
xilman is online now   Reply With Quote
Old 2012-09-29, 11:05   #6
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

787 Posts
Default

Quote:
Originally Posted by xilman View Post
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
diep is offline   Reply With Quote
Old 2012-09-29, 11:42   #7
axn
 
axn's Avatar
 
Jun 2003

153316 Posts
Default

Quote:
Originally Posted by xilman View Post
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.
axn is online now   Reply With Quote
Old 2012-09-29, 12:09   #8
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

787 Posts
Default

Quote:
Originally Posted by axn View Post
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
diep is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Polynomial Discriminant is n^k for an n-1 degree polynomial carpetpool Miscellaneous Math 14 2017-02-18 19:46
TF algorithm(s) davieddy Miscellaneous Math 61 2011-07-06 20:13
Polynomial R.D. Silverman NFSNET Discussion 13 2005-09-16 20:07
aks algorithm and polynomial jocelynl Math 1 2004-02-11 05:20
AKS - A polynomial-time algorithm for testing primality. Maybeso Math 11 2002-11-20 23:39

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


Thu Dec 8 12:03:43 UTC 2022 up 112 days, 9:32, 0 users, load averages: 0.81, 0.81, 0.83

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”