Please help in finding the factor of ...618240007109027021 by the p-1 method...

thanks a lot!

Printable View

- Oct 31st 2009, 11:54 AMVedicmathsnumber theory problem...
Please help in finding the factor of ...618240007109027021 by the p-1 method...

thanks a lot! - Nov 1st 2009, 09:02 AMaidan
n = 618240007109027021

Select a bound for the factorial.

bound = $\displaystyle \ln(n)$ is an acceptable limit.

In this case about 43 .

The exponent will be 43! (factorial of 43)

Choose some number to raise to that exponential value. Any number (a) from 2 to n-1 is useable.

You may want to check that $\displaystyle \gcd(a,n)=1$.

2 is ok.

$\displaystyle r = ( 2^{43!}\mod n )$

$\displaystyle f = \gcd(r-1,n)$

If

$\displaystyle 1<f<n$

then you have a factor of n

If not then raise the bound limit.

In this case one of the factors is a 9 digit number.

The first 3 digits and the last 3 digits are

250___201

.