The p-1 method
The first method to look at is the p-1 method. This method works when p-1 or q-1 factors as a product of small primes. (For this worksheet, small primes ar less than 100.) Without loss of generality assume p-1 factors as a product of small primes. More specifically assume that p-1 divides 100!. Then 2^(100!) mod n is congruent to 1 mod p, and p divides 2^(100!) - 1 mod n. Taking the gcd of that number and n should produce p.
Example 1
Computer Exercise 4 asks you to factor 618240007109027021 by the p-1 method. We compute 2^(100!) mod n.
(Be sure to use
Power (2,100!) mod n
rather than
2^(100!) mod n.
The second tries to compute the power before reducing and will run out of memory. The first reduces mod n at each step.)
| > | n := 618240007109027021; b1 := 100!; t1 := Power(2, b1) mod n; |
Next we find a factor of n. We test if it is prime and see how p-1 factors.
| > | factor1 := igcd(t1-1,n); isprime(factor1); ifactor(factor1-1); |
Finding the other factor is a matter of division. Once again we check if it is priime and find the factors of q-1.
| > | factor2 := n/factor1; isprime(factor2); ifactor(factor2-1); |
Thus 618240007109027021 = (250387201)(2469135821);
Example 2
Computer Exercise 5 asks you to factor 8834884587090814646372459890377418962766907. We repeat the process form above.
| > | n1:=8834884587090814646372459890377418962766907: |
| > | b1 := 100!: t1 := Power(2, b1) mod n1; factor1 := igcd(t1-1, n1); |
| > | factor2 := n1/factor1; |
It is worth noting that this fatcorization gives difficulties to the ifactor command which is not looking for such special cases. When we try using the command we give up and interupt the computation after a while.
| > | ifactor(n1); |
| > |
