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