Polynomial algorithm

[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

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

[xilman]

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?

[diep]

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.

[LaurV]

How about you try it for 29?

[xilman]

Originally Posted by diep

It is different.

I asked how does it differ from Pollard rho?

[diep]

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.

#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.

[axn]

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.

[diep]

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.