Math: Factoring Using the P-1 Method Essay

Factoring 618240007109027021 using the p-1 method

The p-1 method is used to factor primes for instance p & q such that n = p*q and avoid weaknesses in the implementation of the algorithm.

The method works well when q-1 or p-1 can be factored as a product of given small primes.

Therefore to factor 618240007109027021, we first compute;

2^(100!) mod n using Power (2,100!) mod n

In our case;

n := 618240007109027021

a1: = 100!;

t1 : = Power (2,a1) mod n

a1 = 9.3326215443944152681699238856267e+157

t1 = 78737314835659020

Then we find a factor of n, test if it’s prime, and evaluate how p-1 factors;

factor1:= igcd (t1 – 1, n); // use gcd to find the factor

isprime(factor1) //test if factor is prime

ifactor(factor1-1) //if the factor is prime, test how p-1 factors

so factor1 = 250387201

And it’s true (2)⁸ (3)⁵ (5)² (23) (7)

To find the second factor q, we simply divide n by p and also evaluate how q-1 factors;

Factor2:= n/factor1; // divide n by factor1 to obtain q (factor2)

isprime(factor2) //test if q is prime

ifactor(factor2-1) //if the factor is prime, test how q-1 factors

factor2 = 2469135821

And it’s true, (2)² (5) (123456791)

Thus the factors of; 618240007109027021 = (250387201) (2469135821);

Let n be the integer in the computer problem 6.9.4 (page 198)

In this case n = 618240007109027021

Therefore from the above calculations, we obtain the following;

p = 250387201

Therefore the small prime factors of p-1 are

(2)⁸ (3)⁵ (5)² (23) (7)

2) We first select a bound for the factorial.

b = ln (n)

is the acceptable limit.

in this case 43.

Exponent is 43! = 6.0415263063373835637355132068514e+52 (factorial of 43)

then we choose some number to raise to that exponential value.

A number ‘a’ from 2 to n-1 can be used.

In this case, I chose 2

Then that’s a factor of n

If not, raise the bound limit.

P = 250387201

//The function to find the prime factors of n is;

public static BigInteger primefactor(BigInteger n) // n is the integer to factorize

public static BigInteger primefactor(BigInteger n) // n is the integer to factorize

return y.subtract(BigInteger.ONE).gcd(n);}

static void execA()

static void factor(BigInteger n)

public static void main(String[] args) //Main method

}

To factor in a larger value of n, you insert the following method in the code;

static void execB()

execB(); // then call execB() function in main

Factoring n = 642401 using the information;

516107² ≡ 7 (mod n)

And that

187722² ≡ 2² ∙ 7 (mod n)

n = 642401

Therefore factor1 := igcd (516107*187722-2*7, n); // n = 642401

factor1 := 1129

and we obtain factor2 by dividing n by factor1

factor2 := n/factor1;

factor2 := 569

Thus 642401= 1129 * 569 which are indeed primes

given that 2⁽ⁿ⁻¹⁾≡ k²_≡ 1 (mod n)

Then we can deduce from “Fermat’s Little theorem” that n is not indeed a prime

number.

Because 2^(n−1)/2_≡ ±1 (mod n) and 2⁽ⁿ⁻¹⁾≡ 1 (mod n)

then From the “basic factoring principle”; k²≡ 1² (mod n)

and k _≡ ±1 (mod n)

Therefore we can find a nontrivial factor of n using the formula gcd(k-1, n) or gcd(k+1, n)