Changes for page Programming knowledge

Summary

• Page properties (1 modified, 0 added, 0 removed)

Details

Page properties

Content

...	...	@@ -28,7 +28,7 @@
28	28
29	29	{{code language="python"}}
30	30	def a_to_the_b_mod_n(a, b, n):
31		- if b = 0:
	31	+ if b == 0:
32	32	return 1
33	33	if is_even(b):
34	34	return a_to_the_b_mod_n((a * a) % n, b / 2, n)
...	...	@@ -35,4 +35,38 @@
35	35	return (a * a_to_the_b_mod_n(a, b - 1, n)) % n
36	36	{{/code}}
37	37
	38	+= Generating large random prime numbers =
	39	+One of the most powerful features of modern computers is their ability to generate relatively large prime numbers very quickly. To do this, they usually employ the following algorithm:
	40	+
	41	+{{code language="python"}}
	42	+def generate_n_digits_in_length_prime(n):
	43	+ num = generate_n_digits_in_length_number(n)
	44	+ while is_prime(num) == False
	45	+ num = generate_n_digits_in_length_number(n)
	46	+
	47	+{{/code}}
	48	+
	49	+The is_prime function should be an implementation of the Miller-Rabin test, which is the industry standard for testing the primality of large numbers.
	50	+
	51	+== The Miller-Rabin primality test ==
	52	+The Miller-Rabin primality test is an extension of the Miller primality test. Specifically it uses a relatively small number of randomly chosen odd integers that are smaller than N (where N is the number being tested for primality), usually N. If and only if all these tests pass (i.e. they claim that N is prime), then we're to assume that N is prime. The probability of a large number N passing the primality test despite not being prime, when 10 different numbers are randomly chosen to be used, is at most 0.00000095367431640625 (i.e (1/4)^^10^^).
	53	+
	54	+== The Miller primality test ==
	55	+The Miller primality test is an extension of Fermat's Little Theorem.
	56	+
	57	+Specifically, it says that to test a large number N for primality, we are to follow the following steps:
	58	+
	59	+1. Choose a number a smaller than N. This number is a
	60	+1. Compute a^^N^^
	61	+1. Divide the result from the above step by N and check the remainder of that division (i.e. do modulus division). If the remainder is not 1 then the number is composite (i.e. not prime) and stop. If it is 1 but N is odd, it is composite. If it is 1 but N is even, continue to the next step. Keep note of the remainder of this division (i.e. the 1) for later
	62	+1. Divide N by 2. This new number is N'
	63	+1. Compute again a^^N'^^ and then do modulus division against N. Keep note of the remainder again for later. This remainder is to be considered BEFORE in the sequence that we're keeping note of, compared to the 1 calculated in step 3.
	64	+1. Check if N' is odd. If it is, stop. If not, repeat from step 4 onwards, with N' being the new N.
	65	+
	66	+Once the algorithm above is followed, you should have a sequence of numbers that you kept note of. This sequence will determine whether N is indeed prime.
	67	+
	68	+The sequence needs to end in 1. If it does not, N is composite.
	69	+Any number in the sequence before 1 has to be another 1 or N-1. If it is, N is likely prime (although there are false positives!).
	70	+
	71	+
38	38	)))