18569325874132368593842685932487159368246289531783294624855793692581479874563215987532145632896557786932140025693012580390250470294376980316280167902865340150927308605790543904618827030659781028634082987261578853692015937648253869721546083679182056455807629980734658022762958576568709065

Q

Cryptography is heavily dependent on the use of very large PRIME NUMBERS and factorization. Computers are very good at multiplying large numbers. But they are not as good at the opposite, finding the factors or values multiplied together to form the large numbers. This is the concept that modern day cryptography uses in cryptographic algorithms. There are a few exceptions to this concept. Computing factors for some numbers is much easier than others. The use of prime numbers are the building blocks used to create the keys in cryptographic systems. 

P

2/12

59368246289531783294624855793692581479874563215987532145632896557786932140025693012580390250470294376980316280167902865340150927308605790543904618827030659781028185693258741323685938426859324871634082987261578853692015937648253869721546083679182056455807629980734658022762958576568709065

Cryptography and Prime Numbers

Back

Factoring and Prime Numbers

Next

Restart

Next

Factoring and Prime Numbers

This work is licensed with a Creative Commons Attribution 4.0 International LicenseEndFragment

1/12

In mathematics, a factor is a number or algebraic expression that divides another number or expression evenly (or with no remainder). For example, 3 and 6 are factors of 12 because 12 ÷ 3 = 4 exactly and 12 ÷ 6 = 2 exactly. The other factors of 12 are 1, 2, 4, and 12.

Factors 

Enter an integer (1 - 1,000): Submit Next Factors of p:

5/12

Try this exercise to compute the factors of an integer ranging from 1 to 1,000.

Composite NumbersFactors 41,2 and 4 81, 2, 4 and 8 141, 2, 7 and 14 201, 2, 4, 5, 10 and 20 351,5,7 and 35 901,2,3,5,6,9,10,15,18,30,45 and 90 EndFragment

Composite numbers have more that 2 factors. The prime factors of composite numbers are prime numbers such as 2, 3, 5, 7, 11, etc.

8/12

Factors of Composite Numbers

Factorization

Factorization is the process of solving all possible factors for an integer. As an integer gets larger, the factorization process becomes more difficult. Modern cryptographic machines leverage this concept.

Test your factorization skills.Click on the Get Integer button to begin.Enter the factors for each interger.Click to check your answer.Click Get Integer again. Notice how it becomes more difficult as the integer increases:

6/12

Integer: Factors: Get Integer Check Answer

Factors of Square Numbers

7/12

When a number is multiplied by itself, it results in a square number (n x n = n2, where n is any integer).2 x 2 = 22 = 4 (1, 2, 4) 3 x 3 = 32 = 9 (1, 3, 9) 5 x 5 = 52 = 25 (1, 5, 25) 10 x 10 = 102 = 100 (1, 2, 4, 5, 10, 20, 25, 50, 100)One of the factors of a square number is always the original number itself.

Prime numbers have only two factors: 1 and the number itself. You cannot divide a prime number by any other number and have the result be a whole number. Since 1 only has one factor, it is not a prime number.  Prime numbers include 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, and 31. Click the button to generate a table of Prime Numbers.

Prime Numbers

Generate Prime Numbers

3/12

Division Method

10/12

The division method can also be used to find the prime factors by dividing it by a prime number. 

30 / 2 = 15

2 x 2 x 3 x 5

Step 1: Divide the number by the smallest prime number such that the smallest prime number should divide the number completely.  

Click the link to load a Prime Factorization Calculator  

15 / 3 = 5

Let’s start with 60.

Prime Factorization Calculator

 Step 4:  Multiply all the prime factors that are the divisors. 

5 / 5 = 1

Step 3: Since 15 is not divisible by 2, we take the next prime number which is 3. Repeat this step until the quotient is 1.

*Note: the calculator may load in a new window or tab depending on your browser configuration.

60 / 2 = 30

Since we get 1 as the quotient, we stop here.

Step 2: Divide the quotient of step 1 by the smallest prime number. 

Enter an integer (1 - 1,000): Calculate Φ LIST PHI(N) Φ: Numbers Relatively Prime with N:

11/12

Euler defined Phi (represented by the symbol Φ), one of the most important  operations in cryptography because it determines the breakability of a number. Euler discovered that calculating the Φ of a number is difficult as the number get larger. To demonstrate the Φ calcuation:Start with an integer, N.N’s output is the number of integers that are less than or equal to N and do not share any common factors with N.Take  N=8, then find  Φ. The Φ function identifies all values from 1 to 8, then counts how many integers 8 does NOT share a factor greater than 1 with. Recall that the factors of 8 = 1, 2, 4, and 8, so Φ (8) = 4. When you list Φ, notice 6 is not counted because it shares a factor of 2, while 1, 3, 5 and 7 are counted, because they only share a factor of 1.  Enter the integers 6, 7, 9, 10, and 11. Calculate Φ and then list Φ for each. Do you notice a pattern (hint: look at the prime numbers versus the composite numbers)?

Euler’s Totient Function 

x

2

24

4

12

We know that a prime factor is a natural number, other than 1, whose only factors are 1 and itself. We also know that a factor divides evenly into another number without leaving a remainder. Building on those two concepts leads into prime factorization. Prime factorization is the process of writing all numbers as a product of primes. Take the number 24, for example. 24 can break down into two factors, 3 times 8. 3 is a prime number, but 8 is not; 8 is a composite number since it has more than two factors. To break 8 down into just prime number factors, you get 2 x 2 x 2. Threfore, the prime factorization of 24 equals 2 x 2 x 2 x 3. Now look at two different factors of 24, like 2 and 12. 2 is a prime number, but 12 is a composite number. When we break 12 down, we could use 3 x 4. Again, 3 is a prime number, 4 is a composite number, and of course 2 x 2 = 4. Either way you go about it, the prime factorization for 24 is 2 x 2 x 2 x 3.

Factor Tree Method

Prime Factorization

3

8

Click to Factor

9/12

Quiz

Prime Number Quiz

4/12

Public Key

Euler’s Totient 

Private Key

12/12

Did you notice the common pattern for all prime numbers? This is the basis of Euler’s Totient—Φ for any prime number, p, is one less than p. For example:      Φ (3) = 2; Φ (5) = 4; Φ (7) = 6; Φ (9) = 8; Φ (11) = 10Euler's Totient is represented as T. Recall that cryptography uses two large prime numbers to generate a key pair. Therefore, T = (p - 1) x (q - 1) where p and q are a large prime number. To learn more, look for the RSA Encryption Emate.