Math: Factoring Using the P-1 Method Essay

Exclusively available on IvyPanda Available only on IvyPanda

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.

We will write a custom essay on your topic a custom Essay on Math: Factoring Using the P-1 Method
808 writers online

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!;

1 hour!
The minimum time our certified writers need to deliver a 100% original paper

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

Remember! This is just a sample
You can get your custom paper by one of our expert writers

so factor1 = 250387201

And it’s true (2)8 (3)5 (5)2 (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)2 (5) (123456791)

We will write
a custom essay
specifically for you
Get your first paper with
15% OFF

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)8 (3)5 (5)2 (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

Math: Factoring Using the P-1 Method

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;

5161072 ≡ 7 (mod n)

And that

1877222 ≡ 22 ∙ 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(n1)≡ k2_≡ 1 (mod n)

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

number.

Because 2(n1)/2_≡ ±1 (mod n) and 2(n1)1 (mod n)

then From the “basic factoring principle”; k212 (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)

Print
Need an custom research paper on Math: Factoring Using the P-1 Method written from scratch by a professional specifically for you?
808 writers online
Cite This paper
Select a referencing style:

Reference

IvyPanda. (2022, March 16). Math: Factoring Using the P-1 Method. https://ivypanda.com/essays/math-factoring-using-the-p-1-method/

Work Cited

"Math: Factoring Using the P-1 Method." IvyPanda, 16 Mar. 2022, ivypanda.com/essays/math-factoring-using-the-p-1-method/.

References

IvyPanda. (2022) 'Math: Factoring Using the P-1 Method'. 16 March.

References

IvyPanda. 2022. "Math: Factoring Using the P-1 Method." March 16, 2022. https://ivypanda.com/essays/math-factoring-using-the-p-1-method/.

1. IvyPanda. "Math: Factoring Using the P-1 Method." March 16, 2022. https://ivypanda.com/essays/math-factoring-using-the-p-1-method/.


Bibliography


IvyPanda. "Math: Factoring Using the P-1 Method." March 16, 2022. https://ivypanda.com/essays/math-factoring-using-the-p-1-method/.

Powered by CiteTotal, free essay citation generator
If you are the copyright owner of this paper and no longer wish to have your work published on IvyPanda. Request the removal
More related papers
Cite
Print
1 / 1