# [Pkg] The Trunk: Kernel-nice.487.mcz

commits at source.squeak.org commits at source.squeak.org
Thu Sep 2 19:43:15 UTC 2010

```Nicolas Cellier uploaded a new version of Kernel to project The Trunk:
http://source.squeak.org/trunk/Kernel-nice.487.mcz

==================== Summary ====================

Name: Kernel-nice.487
Author: nice
Time: 2 September 2010, 9:42:36.971 pm
UUID: 283f7f22-eafa-42f9-a04d-6919febb4471
Ancestors: Kernel-dtl.486

provide a modular inversion much faster than the binary extended euclidean algorithm found in DigitalSignatureAlgorithm.

As raisedTo:modulo: belongs to Integer, reciprocalModulo: belongs to Integer too. These algorithms have value outside DSA.

=============== Diff against Kernel-dtl.486 ===============

+ ----- 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.
+ 		'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)].
+ 	result := v - f.
+ 	(result2 := result + n) > 0
+ 		ifFalse: [self error: 'no inverse'].
+ 	^result positive
+ 		ifTrue: [result]
+ 		ifFalse: [result2]!

```