repeating random primary test many times makes the result PROBABLY right. a^(p-1) mod p = 1 is always satisfied if p is prime. (a is a random number.) use the calculation for the test. the number of steps doesn't result in so many times but you can know if the number is PROBABLY prime or not.
RSA -> easy to generate public key by two prime numbers multiplications but hard to reverse.also, hard to generate two random prime numbers. there is always limitation of computation time and memory use.
Trial division using sieve helps you decrease number of trials by traversing only prime numbers (using Sieve of Eratosthenes) but there is still memory usage issue because the list of prime numbers is too large.
How can we calculate A^B mod C quickly for any B? e.g. 5^117 mod 19; 117 = 0b1110101; 117 = 2^6+2^5+2^4+2^2+2^0 = 64+32+16+4+1; 5^117 = (5^64+5^32+5^16+5^4+5^1); 5^117 mod 19 = (5^1*5^4*5^16*5^32*5^64) mod 19;
use divide and conquer strategy for making calculation faster. e.g. 2^90 = 2^50 * 2^40; congruence modulo: A≡B (mod C), equivalence: A mod C=B mod C, (A + B) mod C = (A mod C + B mod C) mod C, (A * B) mod C = (A mod C * B mod C) mod C, A^B mod C = ( (A mod C)^B ) mod C
1
Programming Anime: Floyd's Algorithm Explained
What is a Bipartite Graph? | Graph Theory
Fermat primality test
Summary (what's next?) | Journey into cryptography | Computer Science | Khan Academy
Primality test with sieve | Journey into cryptography | Computer Science | Khan Academy
Sieve of Eratosthenes | Journey into cryptography | Computer Science | Khan Academy
Khan Academy
Khan Academy
Khan Academy
