/pliant/util/crypto/intn.pli
1	abstract
2	[A few more functions for the 'Intn' data type: ]
3	[these are 'random' 'prime' 'pgcd' and 'inverse']
4
5
6	module "random.pli"
7
8	constant prime0_fast true
9	constant prime0_maxi 1000
10	constant trace false
11	constant debug false
12
13
14	doc
15	listing
16	function random p -> r
17	arg Intn p r
18	[Returns a strong peuso random number ranging from 0 to p-1.]
19
20	function random p -> r
21	arg Intn p r
22	r binary_decode (random_string (p:nbbits+64)\8) true
23	r apply_modulus p
24
25
26	doc
27	listing
28	function prime p error_probability -> r
29	arg Intn p ; arg Float error_probability ; arg Intn r
30	[Returns a strong peuso random prime number ranging from 0 to p-1.] ; eol
31	[The 'error_probability' should be a very small number such as 1e-30. The smaller it is, the slower the algorithm will be.]
32
33
34	if prime0_fast
35
36	gvar Array:Intn primes
37
38	function prime0 p -> r
39	arg Intn p ; arg Bool r
40	if p<2
41	r := false
42	else
43	for (var Int i) 0 primes:size-1
44	if p%primes:i=0
45	return primes:i>=p
46	r := true
47
48	for (gvar Int uu) 1 prime0_maxi
49	if prime0:uu
50	primes += uu
51
52	else
53
54	function prime0 p -> r
55	arg Intn p ; arg Bool r
56	if p<2
57	return false
58	else
59	var Intn i := 2
60	while i*i<=p and i<prime0_maxi
61	if p%i=0
62	return false
63	i := i+1
64	return true
65
66
67	function prime1 p error_probability -> r
68	arg Intn p ; arg Float error_probability ; arg Bool r
69	var Bool all := true
70	var Float ep := 1
71	if trace
72	var Int count := 0
73	while ep>error_probability
74	if trace
75	console "prime test " count "  [lf]"
76	var Intn a := 1+(random p-1)
77	var Intn b := a^((p-1)\2)%p
78	if b=1
79	void
80	eif b=p-1
81	all := false
82	else
83	return false
84	ep := ep*0.5
85	if trace
86	count := count+1
87	return not all
88
89
90	function prime n error_probability -> r
91	arg Intn n ; arg Float error_probability ; arg Intn r
92	part pick
93	r := random n
94	if debug
95	console "? " r
96	if not prime0:r
97	if debug
98	console " A" eol
99	restart pick
100	if not (prime1 r error_probability)
101	if debug
102	console " B" eol
103	restart pick
104	if debug
105	console " OK" eol
106
107
108	doc
109	listing
110	function pgcd a b -> g
111	arg Intn a b g
112	[Computes the greates commun divisor of both 'a' and 'b'.]
113
114
115	function pgcd a b -> g
116	arg Intn a b g
117	var Intn x := a
118	var Intn y := b
119	g := y
120	while x>0
121	g := x
122	x := y%x
123	y := g
124
125
126	doc
127	listing
128	function inverse x n -> r
129	arg Intn x n r
130	[Finds an inverse 'r' of 'x' modulo 'n'. ] ; eol
131	[It means that x*r mod n = 1]
132
133	function euclide_update un vn q
134	arg_rw Intn un vn ; arg Intn q
135	var Intn tn := un-vn*q
136	un := vn
137	vn := tn
138
139	function euclide u v u1_out u2_out -> r
140	arg Intn u v ; arg_w Intn u1_out u2_out ; arg Intn r
141	var Intn u1 := 1
142	var Intn u3 := u
143	var Intn v1 := 0
144	var Intn v3 := v
145	while v3>0
146	var Intn q := u3\v3
147	euclide_update u1 v1 q
148	euclide_update u3 v3 q
149	u1_out := u1
150	u2_out := (u3-u1*u)\v
151	return u3
152
153	function inverse x n -> r
154	arg Intn x n r
155	var Intn u1 u2
156	var Intn i := euclide x n u1 u2
157	if i<>1
158	return 0
159	eif u1>=0
160	return u1
161	else
162	return u1+n
163
164
165	export random prime pgcd inverse