The Trunk: Kernel-nice.771.mcz
<commits <at> source.squeak.org>
2013-06-18 00:00:00 GMT
Nicolas Cellier uploaded a new version of Kernel to project The Trunk:
http://source.squeak.org/trunk/Kernel-nice.771.mcz
==================== Summary ====================
Name: Kernel-nice.771
Author: nice
Time: 18 June 2013, 11:28:04.495 pm
UUID: e6da6bb0-0aa4-4400-b96c-c53dc343584a
Ancestors: Kernel-fbs.770
Start deprecating usage of \\\
A long comment in \\\ tells the reasons for deprecating
=============== Diff against Kernel-fbs.770 ===============
Item was changed:
----- Method: Integer>>\\\ (in category 'arithmetic') -----
\\\ anInteger
+ "A modulo method former used in DSA."
+
+ "Notes: this method used to be a faster than \\ for LargeIntegers, but this advantage is fainting:
+ - it always was slower for SmallInteger because of the indirection below
+ - a new LargeInteger primitive makes \\ faster up to 64 bits operands
+ - even above 64 bits, its advantage has become marginal thanks to revised \\ primitive fallback code
+ Moreover, \\\ behaviour is questionable for these reasons:
+ - for a negative receiver xor argument, it behaves like rem: for LargeInteger and \\ for SmallInteger
+ - it may answer a not normalized LargeInteger (with leading null digits) which breaks some invariants
+ For example, check (SmallInteger maxVal + 1 \\\ 8) isZero.
+ So beware if you ever think using this method."
- "a modulo method for use in DSA. Be careful if you try to use this elsewhere"
^self \\ anInteger!
Item was changed:
----- Method: Integer>>reciprocalModulo: (in category 'arithmetic') -----
reciprocalModulo: n
"Answer an integer x such that (self * x) \\ n = 1, x > 0, x < n.
Raise an error if there is no such integer.
The algorithm is a non extended euclidean modular inversion called NINV.
It is described in this article:
'Using an RSA Accelerator for Modular Inversion'
by Martin Seysen. See http://www.iacr.org/archive/ches2005/017.pdf"
| u v f fPlusN b result result2 |
((self <= 0) or: [n <= 0]) ifTrue: [self error: 'self and n must be greater than zero'].
self >= n ifTrue: [self error: 'self must be < n'].
b := n highBit + 1.
f := 1 bitShift: b.
v := (self bitShift: b) + 1.
u := n bitShift: b.
fPlusN := f + n.
[v >= fPlusN] whileTrue:
+ [v := u \\ (u := v)].
- [v := u \\\ (u := v)].
result := v - f.
(result2 := result + n) > 0
ifFalse: [self error: 'no inverse'].
^result positive
ifTrue: [result]
ifFalse: [result2]!
Item was changed:
----- Method: Integer>>slidingLeftRightRaisedTo:modulo: (in category 'private') -----
slidingLeftRightRaisedTo: n modulo: m
"Private - compute (self raisedTo: n) \\ m,
Note: this method has to be fast because it is generally used with large integers in cryptography.
It thus operate on exponent bits from left to right by packets with a sliding window rather than bit by bit
(see below)."
| pow j k w index oddPowersOfSelf square |
"Precompute powers of self for odd bit patterns xxxx1 up to length w + 1.
The width w is chosen with respect to the total bit length of n,
such that each bit pattern will on average be encoutered P times in the whole bit sequence of n.
This costs (2 raisedTo: w) multiplications, but more will be saved later (see below)."
k := n highBit.
w := (k highBit - 1 >> 1 min: 16) max: 1.
oddPowersOfSelf := Array new: 1 << w.
oddPowersOfSelf at: 1 put: (pow := self).
+ square := self * self \\ m.
+ 2 to: oddPowersOfSelf size do: [:i | pow := oddPowersOfSelf at: i put: pow * square \\ m].
- square := self * self \\\ m.
- 2 to: oddPowersOfSelf size do: [:i | pow := oddPowersOfSelf at: i put: pow * square \\\ m].
"Now exponentiate by searching precomputed bit patterns with a sliding window"
pow := 1.
[k > 0]
whileTrue:
+ [pow := pow * pow \\ m.
- [pow := pow * pow \\\ m.
"Skip bits set to zero (the sliding window)"
(n bitAt: k) = 0
ifFalse:
["Find longest odd bit pattern up to window length (w + 1)"
j := k - w max: 1.
[j < k and: [(n bitAt: j) = 0]] whileTrue: [j := j + 1].
"We found an odd bit pattern of length k-j+1;
perform the square powers for each bit
(same cost as bitwise algorithm);
compute the index of this bit pattern in the precomputed powers."
index := 0.
[k > j] whileTrue:
+ [pow := pow * pow \\ m.
- [pow := pow * pow \\\ m.
index := index << 1 + (n bitAt: k).
k := k - 1].
"Perform a single multiplication for the whole bit pattern.
This saves up to (k-j) multiplications versus a naive algorithm operating bit by bit"
+ pow := pow * (oddPowersOfSelf at: index + 1) \\ m].
- pow := pow * (oddPowersOfSelf at: index + 1) \\\ m].
k := k - 1].
+ ^pow!
- ^pow normalize!
Item was changed:
----- Method: LargePositiveInteger>>\\\ (in category 'arithmetic') -----
\\\ anInteger
+ "A modulo method former used in DSA.
+ This method is not much faster than \\ and rem: and it breaks some invariants (see super).
+ Usage is now deprecated and should be reserved to backward compatibility."
- "a faster modulo method for use in DSA. Be careful if you try to use this elsewhere"
^(self digitDiv: anInteger neg: false) second!
RSS Feed