--- a/Integer.st Tue Oct 19 01:00:28 1999 +0200
+++ b/Integer.st Tue Oct 19 12:09:43 1999 +0200
@@ -1589,13 +1589,15 @@
^ result
"
- 2 raisedTo:2 mod:3
- 20000000000000 raisedTo:200 mod:190
- (20000000000000 raisedTo:200) \\ 190
+ 2 raisedTo:2 mod:3
+ 20000000000000 raisedTo:200 mod:190
+ (20000000000000 raisedTo:200) \\ 190
+
Time millisecondsToRun:[100 timesRepeat:[
20000000000000 raisedTo:200 mod:190
]
]
+
Time millisecondsToRun:[100 timesRepeat:[
(20000000000000 raisedTo:200) \\ 190
]
@@ -1607,48 +1609,49 @@
!
raisedToCrtModP:p q:q ep:ep eq:eq u:u
-"
- This is a faster modexp for moduli with a known factorisation into two
- relatively prime factors p and q, and an input relatively prime to the
- modulus, the Chinese Remainder Theorem to do the computation mod p and
- mod q, and then combine the results. This relies on a number of
- precomputed values, but does not actually require the modulus n or the
- exponent e.
-
- expout = expin ^ e mod (p*q).
- We form this by evaluating
- p2 = (expin ^ e) mod p and
- q2 = (expin ^ e) mod q
- and then combining the two by the CRT.
-
- Two optimisations of this are possible. First, we can reduce expin
- modulo p and q before starting.
-
- Second, since we know the factorisation of p and q (trivially derived
- from the factorisation of n = p*q), and expin is relatively prime to
- both p and q, we can use Euler's theorem, expin^phi(m) = 1 (mod m),
- to throw away multiples of phi(p) or phi(q) in e.
- Letting ep = e mod phi(p) and
- eq = e mod phi(q)
- then combining these two speedups, we only need to evaluate
- p2 = ((expin mod p) ^ ep) mod p and
- q2 = ((expin mod q) ^ eq) mod q.
-
- Now we need to apply the CRT. Starting with
- expout = p2 (mod p) and
- expout = q2 (mod q)
- we can say that expout = p2 + p * k, and if we assume that 0 <= p2 < p,
- then 0 <= expout < p*q for some 0 <= k < q. Since we want expout = q2
- (mod q), then p*k = q2-p2 (mod q). Since p and q are relatively prime,
- p has a multiplicative inverse u mod q. In other words, u = 1/p (mod q).
-
- Multiplying by u on both sides gives k = u*(q2-p2) (mod q).
- Since we want 0 <= k < q, we can thus find k as
- k = (u * (q2-p2)) mod q.
-
- Once we have k, evaluating p2 + p * k is easy, and
- that gives us the result
-"
+ "Application of the Chinese Remainder Theorem (CRT).
+
+ This is a faster modexp for moduli with a known factorisation into two
+ relatively prime factors p and q, and an input relatively prime to the
+ modulus, the Chinese Remainder Theorem to do the computation mod p and
+ mod q, and then combine the results. This relies on a number of
+ precomputed values, but does not actually require the modulus n or the
+ exponent e.
+
+ expout = expin ^ e mod (p*q).
+ We form this by evaluating
+ p2 = (expin ^ e) mod p and
+ q2 = (expin ^ e) mod q
+ and then combining the two by the CRT.
+
+ Two optimisations of this are possible. First, we can reduce expin
+ modulo p and q before starting.
+
+ Second, since we know the factorisation of p and q (trivially derived
+ from the factorisation of n = p*q), and expin is relatively prime to
+ both p and q, we can use Euler's theorem, expin^phi(m) = 1 (mod m),
+ to throw away multiples of phi(p) or phi(q) in e.
+ Letting ep = e mod phi(p) and
+ eq = e mod phi(q)
+ then combining these two speedups, we only need to evaluate
+ p2 = ((expin mod p) ^ ep) mod p and
+ q2 = ((expin mod q) ^ eq) mod q.
+
+ Now we need to apply the CRT. Starting with
+ expout = p2 (mod p) and
+ expout = q2 (mod q)
+ we can say that expout = p2 + p * k, and if we assume that 0 <= p2 < p,
+ then 0 <= expout < p*q for some 0 <= k < q. Since we want expout = q2
+ (mod q), then p*k = q2-p2 (mod q). Since p and q are relatively prime,
+ p has a multiplicative inverse u mod q. In other words, u = 1/p (mod q).
+
+ Multiplying by u on both sides gives k = u*(q2-p2) (mod q).
+ Since we want 0 <= k < q, we can thus find k as
+ k = (u * (q2-p2)) mod q.
+
+ Once we have k, evaluating p2 + p * k is easy, and
+ that gives us the result
+ "
|result t|
@@ -1712,7 +1715,8 @@
"
- (2 raisedTo:216) asFloat
+ (2 raisedTo:216) asFloat
+ (2 raisedTo:500) raisedTo:500
2 raisedTo:10
-2 raisedTo:10
2 raisedTo:9
@@ -2399,5 +2403,5 @@
!Integer class methodsFor:'documentation'!
version
- ^ '$Header: /cvs/stx/stx/libbasic/Integer.st,v 1.113 1999-10-07 09:54:53 cg Exp $'
+ ^ '$Header: /cvs/stx/stx/libbasic/Integer.st,v 1.114 1999-10-19 10:09:43 cg Exp $'
! !