'From Squeak3.0 of 4 February 2001 [latest update: #3545] on 13 May 2002 at 12:48:51 pm'!
Object subclass: #BinaryOperation
	instanceVariableNames: 'mapping '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Math-Abstract'!
BinaryOperation subclass: #CommutativeBinaryOperation
	instanceVariableNames: ''
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Math-Abstract'!
CommutativeBinaryOperation subclass: #AdditionInZ
	instanceVariableNames: ''
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Math-Examples'!

!AdditionInZ commentStamp: '<historical>' prior: 0!
Standard addition in Z!

CommutativeBinaryOperation subclass: #AdditionInZn
	instanceVariableNames: 'modulus '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Math-Examples'!
Object subclass: #MappingOfSet
	instanceVariableNames: ''
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Math-Abstract'!
CommutativeBinaryOperation subclass: #MultiplicationInNP
	instanceVariableNames: ''
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Math-Examples'!
CommutativeBinaryOperation subclass: #MultiplicationInZn
	instanceVariableNames: 'modulus '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Math-Examples'!
BinaryOperation subclass: #RangedBinaryOperation
	instanceVariableNames: 'range '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Math-Abstract'!
Object subclass: #SemiGroup
	instanceVariableNames: 'basicset addition '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Math-Abstract'!
SemiGroup subclass: #Group
	instanceVariableNames: ''
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Math-Abstract'!
Group subclass: #GroupZn
	instanceVariableNames: ''
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Math-Examples'!
Group subclass: #GroupZnStar
	instanceVariableNames: ''
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Math-Examples'!
GroupZnStar subclass: #GroupRSA
	instanceVariableNames: 'p q '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Math-Examples'!
MappingOfSet subclass: #SetNP
	instanceVariableNames: ''
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Math-Examples'!
MappingOfSet subclass: #SetZ
	instanceVariableNames: ''
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Math-Examples'!
MappingOfSet subclass: #SetZnStar
	instanceVariableNames: 'modulus '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Math-Examples'!
MappingOfSet subclass: #UniversalFiniteSetMapping
	instanceVariableNames: 'myset '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Math-Examples'!

!BinaryOperation methodsFor: 'private' stamp: 'PK 4/8/2002 00:56'!
map: aRealElement
" Map element from its internal representation to the real one "

	^ (self mapping) elementName: aRealElement! !

!BinaryOperation methodsFor: 'private' stamp: 'PK 4/8/2002 00:58'!
mapping
" Returns the mapping used by this set."

	^ mapping
! !

!BinaryOperation methodsFor: 'private' stamp: 'PK 4/8/2002 00:59'!
mapping: aMapping
" Sets the mapping used by this set.  This method should be never called from outside, use
  initializeMapping."

	^ mapping := aMapping
! !

!BinaryOperation methodsFor: 'private' stamp: 'PK 4/8/2002 00:56'!
unmap: anElement
" Map element from its real representation to the internal one "

	^ (self mapping) elementIndex: anElement! !

!BinaryOperation methodsFor: 'as yet unclassified' stamp: 'PK 5/13/2002 00:31'!
initializeMapping: aMapping
" Sets the new mapping for this instance.  If the mapping is finite, recomputes the important properties of the operation (neutral elements, inverses, etc. )"

	self mapping: aMapping.
	(aMapping isenumerable) ifTrue: [ ].
	^ aMapping
		! !

!BinaryOperation methodsFor: 'as yet unclassified' stamp: 'PK 4/8/2002 02:37'!
invert: anElement
" Proxy object for inverse operation"

	^ self map: ( self realInvert: (self unmap: anElement))
! !

!BinaryOperation methodsFor: 'as yet unclassified' stamp: 'PK 4/8/2002 01:14'!
isElement: anElement inverseOf: anElement2
" Answers the question: 'Is anElement inverse of anElement2?'"

	^ (self isElement: anElement leftInverseOf: anElement2) and:
       [self isElement: anElement rightInverseOf: anElement2 ]! !

!BinaryOperation methodsFor: 'as yet unclassified' stamp: 'PK 4/8/2002 01:31'!
isElement: anElement leftInverseOf: anElement2
" Answers the question: 'Is anElement left inverse of anElement2?'"

	^ self isElementLeftNeutral: (self operateOn: anElement and: anElement2)! !

!BinaryOperation methodsFor: 'as yet unclassified' stamp: 'PK 4/8/2002 01:43'!
isElement: anElement rightInverseOf: anElement2
" Answers the question: 'Is anElement right inverse of anElement2?'"

	^ self isElementRightNeutral: (self operateOn: anElement2 and: anElement)! !

!BinaryOperation methodsFor: 'as yet unclassified' stamp: 'PK 4/16/2002 11:16'!
isElementLeftNeutral: anElement
" Proxy object for answering: 'Is anElement is a left neutral element ?'"

	^ self isRealElementLeftNeutral: (self unmap: anElement)! !

!BinaryOperation methodsFor: 'as yet unclassified' stamp: 'PK 4/8/2002 01:32'!
isElementNeutral: anElement
" Answers true if anElement is a (left and right) neutral element"

	^ (self isElementLeftNeutral: anElement) and: [ self isElementRightNeutral: anElement ]! !

!BinaryOperation methodsFor: 'as yet unclassified' stamp: 'PK 4/8/2002 02:38'!
isElementRightNeutral: anElement
" Proxy object for answering: 'Is anElement is a Right neutral element ?'"

	^ self isRealElementRightNeutral: (self unmap: anElement)! !

!BinaryOperation methodsFor: 'as yet unclassified' stamp: 'PK 4/8/2002 02:38'!
leftInvert: anElement
" Proxy object: returns left inverse anElement if it exists, otherwise returns nil."

	^ self map: (self realLeftInvert: (self unmap: anElement))! !

!BinaryOperation methodsFor: 'as yet unclassified' stamp: 'PK 4/8/2002 02:38'!
leftNeutral
" Proxy object: Returns the first left neutral element of the operation; if there is none, return nil"

	^ self map: (self realLeftNeutral)! !

!BinaryOperation methodsFor: 'as yet unclassified' stamp: 'PK 4/8/2002 02:38'!
neutral
" Returns the first neutral element of the operation; if there is none, return nil"

	^ self map: (self realNeutral)! !

!BinaryOperation methodsFor: 'as yet unclassified' stamp: 'PK 4/8/2002 02:38'!
operateOn: anElement1 and: anElement2
" Basic method of every operation - return the result of the binary operation on pair of
  elements.  This is just a proxy method for the real operation (realOperateOn)"

	^ self map: (self realOperateOn: (self unmap: anElement1) and: (self unmap: anElement2))
! !

!BinaryOperation methodsFor: 'as yet unclassified' stamp: 'PK 4/8/2002 02:38'!
rightInvert: anElement
" Proxy object: returns right inverse anElement if it exists, otherwise returns nil."

	^ self map: (self realRightInvert: (self unmap: anElement))! !

!BinaryOperation methodsFor: 'as yet unclassified' stamp: 'PK 4/8/2002 02:38'!
rightNeutral
" Proxy object: Returns the first right neutral element of the operation; if there is none, return nil"

	^ self map: (self realRightNeutral)! !

!BinaryOperation methodsFor: 'as yet unclassified' stamp: 'PK 4/6/2002 02:16'!
square: anElement

	^ self operateOn: anElement and: anElement
! !

!BinaryOperation methodsFor: 'real methods' stamp: 'PK 4/16/2002 11:27'!
isCommutative

	^ false! !

!BinaryOperation methodsFor: 'real methods' stamp: 'PK 4/8/2002 01:46'!
isRealElementLeftNeutral: anElement
" Answers true if anElement is a left neutral element"

	^ self subclassResponsibility! !

!BinaryOperation methodsFor: 'real methods' stamp: 'PK 4/8/2002 01:49'!
isRealElementRightNeutral: anElement
" Answers true if anElement is a right neutral element"

	^ self subclassResponsibility! !

!BinaryOperation methodsFor: 'real methods' stamp: 'PK 4/8/2002 01:39'!
realInvert: anElement
" Returns the inverse of the element."

	^ self subclassResponsibility
! !

!BinaryOperation methodsFor: 'real methods' stamp: 'PK 4/8/2002 01:45'!
realLeftInvert: anElement
" Returns the left inverse of the element."

	^ self subclassResponsibility
! !

!BinaryOperation methodsFor: 'real methods' stamp: 'PK 4/8/2002 01:54'!
realLeftNeutral
" Returns the left neutral element of the set."

	^ self subclassResponsibility! !

!BinaryOperation methodsFor: 'real methods' stamp: 'PK 4/8/2002 01:53'!
realNeutral
" Returns the neutral element of the set."

	^ self subclassResponsibility! !

!BinaryOperation methodsFor: 'real methods' stamp: 'PK 4/8/2002 00:53'!
realOperateOn: aRealElement1 and: aRealElement2
" Real version of the operation - return the result of the binary operation on pair of
  elements in its internal representation.  This is the real method to be overriden in subclasses"

	^ self subclassResponsibility

! !

!BinaryOperation methodsFor: 'real methods' stamp: 'PK 4/8/2002 01:45'!
realRightInvert: anElement
" Returns the right inverse of the element."

	^ self subclassResponsibility
! !

!BinaryOperation methodsFor: 'real methods' stamp: 'PK 4/8/2002 01:54'!
realRightNeutral
" Returns the right neutral element of the set."

	^ self subclassResponsibility! !

!BinaryOperation methodsFor: 'subSet operations' stamp: 'PK 4/8/2002 01:12'!
invert: anElement inASet: aSet
" Returns the inverse of element anElement in set aSet, if such element exists; otherwise returns nil."

	aSet do:
		[: i | (self isElement: i inverseOf: anElement inSet: aSet) ifTrue: [ ^ i ] ].
	^ nil

	! !

!BinaryOperation methodsFor: 'subSet operations' stamp: 'PK 4/8/2002 01:09'!
isClosedOnSet: aSet
" Answers true tf the operation is closed on a set elements.  This method is ineffective and should be overriden in subclasses"

	aSet do:
		[: i | aSet do:
			[: j | (aSet includes: (self operateOn: i and: j)) ifFalse: [ ^ false ]]].
	^ true! !

!BinaryOperation methodsFor: 'subSet operations' stamp: 'PK 4/8/2002 01:10'!
isCommutativeOnSet: aSet
" Answers true tf the operation is commutative on a set elements.  This method is ineffective and should be overriden in subclasses"

	aSet do:
		[: i | aSet do:
			[: j | ((self operateOn: i and: j) = (self operateOn: j and: i)) ifFalse: [ ^ false ]]].
	^ true! !

!BinaryOperation methodsFor: 'subSet operations' stamp: 'PK 4/22/2002 02:20'!
isElement: anElement leftInverseOf: anElement2 inSet: aSet
" Answers true if anElement is left inverse of anElement2 in the set aSet. "

	^ self isElement: (self operateOn: anElement and: anElement2) leftNeutralInSet: aSet
! !

!BinaryOperation methodsFor: 'subSet operations' stamp: 'PK 4/22/2002 02:36'!
isElement: anElement leftNeutralInSet: aSet
" Answers true if anElement is left neutral element (left zero) of the operation inf the set aSet. This method is ineffective and should be overriden in subclasses."

	aSet do:
		[: i | ((self operateOn: anElement and: i) = i) ifFalse: [ ^ false ]].
	^ true
! !

!BinaryOperation methodsFor: 'subSet operations' stamp: 'PK 4/8/2002 01:19'!
isElement: anElement neutralInSet: aSet
" Answers true if anElement is a (left and right) neutral element in a set aSet"

	^ (self isElement: anElement leftNeutralInSet: aSet) and:
       [self isElement: anElement rightNeutralInSet: aSet]! !

!BinaryOperation methodsFor: 'subSet operations' stamp: 'PK 4/22/2002 02:21'!
isElement: anElement rightInverseOf: anElement2 inSet: aSet
" Answers true if anElement is right inverse of anElement2 in the set aSet. "

	^ self isElement: (self operateOn: anElement2 and: anElement) rightNeutralInSet: aSet
! !

!BinaryOperation methodsFor: 'subSet operations' stamp: 'PK 4/22/2002 02:36'!
isElement: anElement rightNeutralInSet: aSet
" Answers true if anElement is left neutral element (left zero) of the operation in the set aSet. This method is  ineffective and should be overriden in subclasses."

	aSet do:
		[: i | ((self operateOn: i and: anElement) = i) ifFalse: [ ^ false ]].
	^ true! !

!BinaryOperation methodsFor: 'subSet operations' stamp: 'PK 4/22/2002 02:30'!
isLeftBijectionOnSet: aSet
" Returns true iff the operation is left bijection on set = if for every element is left multiplication by it a bijection."

	aSet do: 
		[: i | ((self leftInvert: i inASet: aSet) isNil) ifTrue: [ ^ false ]].
	^ true! !

!BinaryOperation methodsFor: 'subSet operations' stamp: 'PK 4/22/2002 02:30'!
isRightBijectionOnSet: aSet
" Returns true iff the operation is right bijection on set = if for every element is right multiplication by it a bijection."

	aSet do: 
		[: i | ((self rightInvert: i inASet: aSet) isNil) ifTrue: [ ^ false ]].
	^ true! !

!BinaryOperation methodsFor: 'subSet operations' stamp: 'PK 4/22/2002 02:23'!
leftInvert: anElement inASet: aSet
" Returns the left inverse of element anElement in set aSet, if such element exists; otherwise returns nil."

	aSet do:
		[: i | (self isElement: i leftInverseOf: anElement inSet: aSet) ifTrue: [ ^ i ] ].
	^ nil

	! !

!BinaryOperation methodsFor: 'subSet operations' stamp: 'PK 4/16/2002 11:13'!
leftNeutralInSet: aSet
" Returns the left neutral element for set aSet." 

	aSet do:
		[: i | (self isElement: i leftNeutralInSet: aSet) ifTrue: [ ^ i ] ].
	^ nil
! !

!BinaryOperation methodsFor: 'subSet operations' stamp: 'PK 4/16/2002 11:13'!
neutralInSet: aSet
" Returns the neutral element for set aSet." 

	aSet do:
		[: i | (self isElement: i neutralInSet: aSet) ifTrue: [ ^ i ] ].
	^ nil
! !

!BinaryOperation methodsFor: 'subSet operations' stamp: 'PK 4/22/2002 02:24'!
rightInvert: anElement inASet: aSet
" Returns the right inverse of element anElement in set aSet, if such element exists; otherwise returns nil."

	aSet do:
		[: i | (self isElement: i rightInverseOf: anElement inSet: aSet) ifTrue: [ ^ i ] ].
	^ nil

	! !

!BinaryOperation methodsFor: 'subSet operations' stamp: 'PK 4/16/2002 11:14'!
rightNeutralInSet: aSet
" Returns the left neutral element for set aSet." 

	aSet do:
		[: i | (self isElement: i rightNeutralInSet: aSet) ifTrue: [ ^ i ] ].
	^ nil
! !


!BinaryOperation class methodsFor: 'instance creation' stamp: 'PK 4/8/2002 01:06'!
new

	^ self error: 'A binary operation needs a set !!'! !

!BinaryOperation class methodsFor: 'instance creation' stamp: 'PK 4/8/2002 02:31'!
new: aSet

	| NewInstance |
	NewInstance := super new.
	NewInstance initializeMapping: aSet.
	^ NewInstance! !


!CommutativeBinaryOperation methodsFor: 'as yet unclassified' stamp: 'PK 4/22/2002 02:04'!
isCommutative

	^ true! !

!CommutativeBinaryOperation methodsFor: 'as yet unclassified' stamp: 'PK 4/22/2002 02:06'!
isRealElementLeftNeutral: anElement

	^ self isRealElementNeutral: anElement! !

!CommutativeBinaryOperation methodsFor: 'as yet unclassified' stamp: 'PK 4/22/2002 02:06'!
isRealElementNeutral: anElement

	^ self subclassResponsibility.
! !

!CommutativeBinaryOperation methodsFor: 'as yet unclassified' stamp: 'PK 4/22/2002 02:06'!
isRealElementRightNeutral: anElement

	^ self isRealElementNeutral: anElement! !

!CommutativeBinaryOperation methodsFor: 'as yet unclassified' stamp: 'PK 4/22/2002 02:04'!
realLeftInvert: anElement

	^ self realInvert: anElement
! !

!CommutativeBinaryOperation methodsFor: 'as yet unclassified' stamp: 'PK 4/22/2002 02:05'!
realLeftNeutral

	^ self realNeutral.! !

!CommutativeBinaryOperation methodsFor: 'as yet unclassified' stamp: 'PK 4/22/2002 02:04'!
realRightInvert: anElement

	^ self realRightInvert: anElement
! !

!CommutativeBinaryOperation methodsFor: 'as yet unclassified' stamp: 'PK 4/22/2002 02:05'!
realRightNeutral

	^ self realNeutral.! !


!AdditionInZ methodsFor: 'as yet unclassified' stamp: 'PK 4/22/2002 02:07'!
isRealElementNeutral: anElement

	^ anElement = 0
! !

!AdditionInZ methodsFor: 'as yet unclassified' stamp: 'PK 4/8/2002 02:01'!
realInvert: anElement

	^ (anElement negated)! !

!AdditionInZ methodsFor: 'as yet unclassified' stamp: 'PK 4/8/2002 01:58'!
realNeutral

	^ 0! !

!AdditionInZ methodsFor: 'as yet unclassified' stamp: 'PK 4/8/2002 01:36'!
realOperateOn: aNumber and: aNumber2

	^ aNumber + aNumber2! !


!AdditionInZn methodsFor: 'as yet unclassified' stamp: 'PK 4/8/2002 02:29'!
initialize: anInteger

	self modulus: anInteger.
	^ self! !

!AdditionInZn methodsFor: 'as yet unclassified' stamp: 'PK 4/22/2002 02:07'!
isRealElementNeutral: anElement

	^ anElement = 0
! !

!AdditionInZn methodsFor: 'as yet unclassified' stamp: 'PK 5/12/2002 21:36'!
modulus

	^ modulus
! !

!AdditionInZn methodsFor: 'as yet unclassified' stamp: 'PK 4/6/2002 02:28'!
modulus: anInteger

	(anInteger isInteger) ifFalse: [ ^ self error: 'Modulus must be an integer !!' ] .
	(anInteger >= 1) ifFalse: [ ^ self error: 'Modulus must be at least one !!' ].
	^ modulus := anInteger
! !

!AdditionInZn methodsFor: 'as yet unclassified' stamp: 'PK 5/12/2002 21:37'!
realInvert: anElement

	^ (modulus - anElement) \\ modulus.
! !

!AdditionInZn methodsFor: 'as yet unclassified' stamp: 'PK 5/12/2002 21:36'!
realNeutral

	^ 0
! !

!AdditionInZn methodsFor: 'as yet unclassified' stamp: 'PK 4/8/2002 02:03'!
realOperateOn: anElement and: anElement2

	^ (anElement + anElement2) \\ (self modulus)
	! !


!AdditionInZn class methodsFor: 'as yet unclassified' stamp: 'PK 5/12/2002 21:36'!
new

	^ self error: 'Zn needs modulus' ! !

!AdditionInZn class methodsFor: 'as yet unclassified' stamp: 'PK 4/8/2002 02:29'!
new: aSet with: anInteger

	^ (super new: aSet) initialize: anInteger
 ! !


!HtmlTableDataItem methodsFor: 'formatting' stamp: 'PK 5/13/2002 01:35'!
addToFormatter: formatter
	super addToFormatter: formatter.
	formatter ensureSpaces: 1.! !


!Integer methodsFor: 'testing' stamp: 'PK 5/12/2002 23:59'!
isFermatPRPInBase: aBase
" Am I Fermat PRP for base aBase ?  Uses multiplicative group Zn*."

	| SZ |

" If aBase is 0 mod N, N can be a prime."
	(aBase \\ self = 0) ifTrue: [ ^ true ].
" Otherwise, if aBase shares a non-trivial common factor with N, neither of them can be a prime"
	((self gcd: aBase) > 1) ifTrue: [ ^ false ].
" If aBase is coprime to N, use the main test."
	SZ := GroupZnStar new: self.
	^ SZ isFermatPRPBase: (aBase \\ self).
! !

!Integer methodsFor: 'mathematical functions' stamp: 'PK 5/12/2002 23:39'!
extendedGcd: aNumber
" Returns a triple - result of the extended Euclid gcd algorithm applied to myself and aNumber" 

	| z |

	(self > aNumber) ifTrue: [
		z := aNumber extendedGcd: self.
		^ { z at: 1. z at: 3. z at: 2. }
		].
	(self = 0) ifTrue: [ ^ {aNumber . 0 . 1} ].
	z := (aNumber \\ self ) extendedGcd: self.
	^ {(z at: 1) . ((z at: 3) - ((z at: 2)*(aNumber // self))) . (z at: 2)}
! !


!MappingOfSet methodsFor: 'as yet unclassified' stamp: 'PK 5/12/2002 20:36'!
domain
" Returns the domain of the mapping in the case of enumerable finite mappings, else answers with nil.  In general, should be overriden by subclasses to reflect their properties."

	^ nil
! !

!MappingOfSet methodsFor: 'as yet unclassified' stamp: 'PK 5/12/2002 20:36'!
elementIndex: aName
" Maps a element from its external representation to internal one.  This MUST be overriden in subclasses."

	^ self subclassResponsibility! !

!MappingOfSet methodsFor: 'as yet unclassified' stamp: 'PK 5/12/2002 20:37'!
elementName: anIndex
" Maps a element from its internal representation to external one.  This MUST be overriden in subclasses."

	^ self subclassResponsibility
! !

!MappingOfSet methodsFor: 'as yet unclassified' stamp: 'PK 5/13/2002 00:28'!
isenumerable
" Returns the enumerability of the set (ie, Is the set effectively enumerable ?  In general, this method should be override in subclasses."

	^ false! !

!MappingOfSet methodsFor: 'as yet unclassified' stamp: 'PK 5/12/2002 20:37'!
isfinite
" Returns the finiteness of the mapping."

	^ self numberOfElements notNil! !

!MappingOfSet methodsFor: 'as yet unclassified' stamp: 'PK 5/13/2002 00:28'!
numberOfElements
" Returns the number of elements of mapping's domain. In general, this is the size of its domain, unless the domain is non-enumerable.  In the latter case, the mapping should return size of its real domain (if finite)."

	(self isenumerable) ifFalse: [ ^ nil ].
	^ (self domain size).
! !


!MultiplicationInNP methodsFor: 'as yet unclassified' stamp: 'PK 4/22/2002 02:08'!
isRealElementNeutral: anElement

	^ anElement = 1
! !

!MultiplicationInNP methodsFor: 'as yet unclassified' stamp: 'PK 4/22/2002 02:01'!
realInvert: anElement

	(anElement = 1)
		ifTrue: [ ^ 1. ]
		ifFalse: [ ^ nil. ].
! !

!MultiplicationInNP methodsFor: 'as yet unclassified' stamp: 'PK 4/22/2002 01:59'!
realNeutral

	^ 1! !

!MultiplicationInNP methodsFor: 'as yet unclassified' stamp: 'PK 4/22/2002 02:09'!
realOperateOn: aNumber and: aNumber2

	^ aNumber * aNumber2! !


!MultiplicationInZn methodsFor: 'as yet unclassified' stamp: 'PK 4/22/2002 02:11'!
initialize: anInteger

	self modulus: anInteger.
	^ self! !

!MultiplicationInZn methodsFor: 'as yet unclassified' stamp: 'PK 5/13/2002 00:30'!
isClosedOnSet: aSet

	(self mapping isenumerable) ifFalse: [ ^ true ].
	(aSet = (self mapping domain))
		ifTrue: [ ^ true. ]
		ifFalse: [ ^ super isClosedOnASet: aSet ].
! !

!MultiplicationInZn methodsFor: 'as yet unclassified' stamp: 'PK 4/22/2002 03:06'!
isRealElementNeutral: anElement

	^ anElement = 1
! !

!MultiplicationInZn methodsFor: 'as yet unclassified' stamp: 'PK 5/12/2002 21:41'!
modulus

	^ modulus
! !

!MultiplicationInZn methodsFor: 'as yet unclassified' stamp: 'PK 5/12/2002 21:41'!
modulus: anInteger

	(anInteger isInteger) ifFalse: [ ^ self error: 'Modulus must be an integer !!' ] .
	(anInteger >= 1) ifFalse: [ ^ self error: 'Modulus must be at least two !!' ].
	^ modulus := anInteger
! !

!MultiplicationInZn methodsFor: 'as yet unclassified' stamp: 'PK 5/13/2002 02:22'!
realInvert: anElement

	^ ((anElement extendedGcd: (self modulus)) at: 2) \\ modulus.
! !

!MultiplicationInZn methodsFor: 'as yet unclassified' stamp: 'PK 5/12/2002 21:43'!
realNeutral

	^ 1
! !

!MultiplicationInZn methodsFor: 'as yet unclassified' stamp: 'PK 4/22/2002 03:06'!
realOperateOn: anElement and: anElement2

	^ (anElement * anElement2) \\ (self modulus) 
	! !


!MultiplicationInZn class methodsFor: 'as yet unclassified' stamp: 'PK 5/12/2002 21:41'!
new

	^ self error: 'Zn* needs modulus' ! !

!MultiplicationInZn class methodsFor: 'as yet unclassified' stamp: 'PK 4/22/2002 02:11'!
new: aSet with: anInteger

	^ (super new: aSet) initialize: anInteger
 ! !


!RangedBinaryOperation methodsFor: 'private' stamp: 'PK 4/6/2002 00:02'!
range
	^ range! !

!RangedBinaryOperation methodsFor: 'private' stamp: 'PK 4/6/2002 02:20'!
range: aRange

	^ range := aRange! !

!RangedBinaryOperation methodsFor: 'real methods' stamp: 'PK 4/16/2002 11:28'!
isCommutative

	^ self isCommutativeOnSet: (self range)
! !

!RangedBinaryOperation methodsFor: 'real methods' stamp: 'PK 4/16/2002 11:23'!
isRealElementLeftNeutral: anElement

	^ self isElement: anElement leftNeutralInSet: (self range)! !

!RangedBinaryOperation methodsFor: 'real methods' stamp: 'PK 4/16/2002 11:23'!
isRealElementRightNeutral: anElement

	^ self isElement: anElement rightNeutralInSet: (self range)! !

!RangedBinaryOperation methodsFor: 'real methods' stamp: 'PK 4/16/2002 11:25'!
realInvert: anElement

	^ self invert: anElement inASet: (self range)
! !

!RangedBinaryOperation methodsFor: 'real methods' stamp: 'PK 4/16/2002 11:28'!
realLeftInvert: anElement

	^ self leftInvert: anElement inASet: (self range)! !

!RangedBinaryOperation methodsFor: 'real methods' stamp: 'PK 4/16/2002 11:29'!
realLeftNeutral

	^ self leftNeutralInSet: (self range)
! !

!RangedBinaryOperation methodsFor: 'real methods' stamp: 'PK 4/16/2002 11:30'!
realNeutral

	^ self neutralInSet: (self range)
! !

!RangedBinaryOperation methodsFor: 'real methods' stamp: 'PK 4/16/2002 11:29'!
realRightInvert: anElement

	^ self rightInvert: anElement inASet: (self range)! !

!RangedBinaryOperation methodsFor: 'real methods' stamp: 'PK 4/16/2002 11:29'!
realRightNeutral

	^ self rightNeutralInSet: (self range)
! !


!RangedBinaryOperation class methodsFor: 'as yet unclassified' stamp: 'PK 4/16/2002 11:22'!
new: aSet

	(aSet isfinite) ifFalse: [ ^ self error: 'I am a RANGED operation !!' ].
	^ super new range: (aSet domain)! !


!SemiGroup methodsFor: 'private' stamp: 'PK 4/6/2002 00:31'!
addition: anOperation
	^ addition := anOperation! !

!SemiGroup methodsFor: 'private' stamp: 'PK 4/6/2002 00:31'!
basicset: aSet
	^ basicset := aSet
	! !

!SemiGroup methodsFor: 'private' stamp: 'PK 5/13/2002 00:30'!
initialize: aSet withInst: anOperation

"If the set if finite, we'll verify and calculate all its properties.  Otherwise ..."
	(aSet isenumerable) ifTrue: [
		" Verification"
		(anOperation isClosedOnSet: (aSet domain)) ifFalse: [ self error: 'I need a closed operation !!' ].
		" And calculation" 
		].
	self basicset: aSet.
	self addition: anOperation.
	^ self! !

!SemiGroup methodsFor: 'private' stamp: 'PK 5/13/2002 01:36'!
multiplicativeTable

	| D T HB Url |

	(self basicset domain isNil) ifTrue: [ ^ nil ].
	D := self basicset domain.
	T := '<html><head><title>Multiplicative Table</title></head>
<body><table caption=Multiplicative Table border=1>
<tr><td>*</td>'.
	D do: [ :a |	T := T, '<td><b>', a asString, '</b></td>'. ].
	T := T, '</tr>
'.
	D do: [ :a |
		T := T, '<tr><td><b>', a asString, '</b></td>'.
		D do: [ :b | T := T, '<td>', (self operateOn: a and: b) asString, '</td>'. ].
		T := T, '</tr>
'.
		].
	T := T, '</table></body></html>
'.
	HB := Scamper new.
	Url := MIMEDocument contentType: 'text/html' content: T url: (FileUrl absoluteFromText: 'AS.MultiplicativeTable').
	HB displayTextHtmlPage: Url.
	HB openAsMorph.
	^ T
! !

!SemiGroup methodsFor: 'as yet unclassified' stamp: 'PK 4/6/2002 00:20'!
operateOn: anElement1 and: anElement2
	^ self addition operateOn: anElement1 and: anElement2
! !

!SemiGroup methodsFor: 'accessing' stamp: 'PK 4/6/2002 00:15'!
addition
	^ addition! !

!SemiGroup methodsFor: 'accessing' stamp: 'PK 4/6/2002 00:14'!
basicset
	^ basicset! !

!SemiGroup methodsFor: 'accessing' stamp: 'PK 4/16/2002 11:55'!
initialize: aSet with: anOperation

	self initialize: aSet withInst: (anOperation new: aSet).
	^ self! !

!SemiGroup methodsFor: 'accessing' stamp: 'PK 4/16/2002 11:49'!
invert: anElement

	^ self addition invert: anElement
! !

!SemiGroup methodsFor: 'accessing' stamp: 'PK 4/16/2002 11:49'!
leftInvert: anElement

	^ self addition leftInvert: anElement
! !

!SemiGroup methodsFor: 'accessing' stamp: 'PK 4/16/2002 11:49'!
leftNeutral

	^ self addition leftNeutral
! !

!SemiGroup methodsFor: 'accessing' stamp: 'PK 4/16/2002 11:48'!
neutral

	^ self addition neutral
! !

!SemiGroup methodsFor: 'accessing' stamp: 'PK 4/16/2002 11:43'!
raiseElement: anElement toPower: anInteger

	|z|
	(anInteger isInteger) ifFalse: [ ^ self error: 'Semigroup exponentiation is defined only for integer exponents' ].
	(anInteger = 1) ifTrue: [ ^ anElement ].
	(anInteger > 1) ifTrue:
		[ (anInteger even)
			ifTrue: [ ^ addition square: (self raiseElement: anElement toPower: (anInteger//2)) ]
			ifFalse: [ ^ addition operateOn: anElement and: (addition square: (self raiseElement: anElement toPower: (anInteger//2))) ]
		].
	(anInteger = 0) ifTrue:
		[ z := addition neutral.
		  (z isNil) ifTrue: [ ^ self error: 'Element exponentiated to zero with no neutral' ]
			       ifFalse: [ ^ z ]
		].
	z:=addition invert: anElement.
	(z isNil)
		ifTrue: [ ^ self error: 'Element exponentiated to negative power has no inverse' ]
		ifFalse: [ ^ self raiseElement: z toPower: (anInteger negated) ].
! !

!SemiGroup methodsFor: 'accessing' stamp: 'PK 4/16/2002 11:49'!
rightInvert: anElement

	^ self addition rightInvert: anElement
! !

!SemiGroup methodsFor: 'accessing' stamp: 'PK 4/16/2002 11:50'!
rightNeutral

	^ self addition rightNeutral
! !


!Group methodsFor: 'as yet unclassified' stamp: 'PK 5/13/2002 00:29'!
initialize: aSet withInst: anOperation

"If the set if finite, we'll verify and calculate all its properties.  Otherwise ..."
	(aSet isenumerable) ifTrue: [
		(anOperation isLeftBijectionOnSet: (aSet domain)) ifFalse: [ ^ self error: 'I need a left bijective operation.' ].
		(anOperation isRightBijectionOnSet: (aSet domain)) ifFalse: [ ^ self error: 'I need a right bijective operation.' ].
		].

	^ super initialize: aSet withInst: anOperation
! !


!GroupZnStar methodsFor: 'as yet unclassified' stamp: 'PK 4/22/2002 03:20'!
isFermatPRPBase: aNumber

	^ self addition isElementNeutral: (self raiseElement: aNumber toPower: (self addition modulus-1))! !

!GroupZnStar methodsFor: 'as yet unclassified' stamp: 'PK 5/11/2002 16:22'!
modulus

	^ self addition modulus! !


!GroupRSA methodsFor: 'as yet unclassified' stamp: 'PK 5/13/2002 02:08'!
decrypt: aMessage with: aKey

	((aMessage gcd: (p*q)) = 1) ifFalse: [ ^ self error: 'This version requires message to be coprime to N' ].
	(aMessage between: 0 and: (p*q-1)) ifFalse: [ ^ self error: 'This version requires message to be less than N' ].
	^ self raiseElement: aMessage toPower: aKey.


	! !

!GroupRSA methodsFor: 'as yet unclassified' stamp: 'PK 5/13/2002 02:08'!
encrypt: aMessage with: aKey

	(self verifyKey: aKey) ifFalse: [ ^ self error: 'RSA key must be coprime to (p-1)(q-1)!!' ].
	((aMessage gcd: (p*q)) = 1) ifFalse: [ ^ self error: 'This version requires message to be coprime to N' ].
	(aMessage between: 0 and: (p*q-1)) ifFalse: [ ^ self error: 'This version requires message to be less than N' ].
	^ self raiseElement: aMessage toPower: aKey.


	! !

!GroupRSA methodsFor: 'as yet unclassified' stamp: 'PK 5/13/2002 01:58'!
initialize: aPi and: aQue

	self p: aPi.
	self q: aQue.
	^ self
	! !

!GroupRSA methodsFor: 'as yet unclassified' stamp: 'PK 5/13/2002 02:19'!
makeDecryptionKey: aKey

	(self verifyKey: aKey) ifFalse: [ ^ self error: 'A key must be coprime to (p-1)(q-1).' ].
	^ (GroupZnStar new: (self p-1)*(self q-1)) invert: aKey.



	! !

!GroupRSA methodsFor: 'as yet unclassified' stamp: 'PK 5/13/2002 01:54'!
p

	^ p! !

!GroupRSA methodsFor: 'as yet unclassified' stamp: 'PK 5/13/2002 01:55'!
p: aPi

	^ p := aPi.! !

!GroupRSA methodsFor: 'as yet unclassified' stamp: 'PK 5/13/2002 01:54'!
q

	^ q! !

!GroupRSA methodsFor: 'as yet unclassified' stamp: 'PK 5/13/2002 01:55'!
q: aQue

	^ q := aQue.! !

!GroupRSA methodsFor: 'as yet unclassified' stamp: 'PK 5/13/2002 02:02'!
verifyKey: aKey

	^ ((aKey gcd: ((self p-1)*(self q-1))) = 1)
! !


!SemiGroup class methodsFor: 'as yet unclassified' stamp: 'PK 4/6/2002 00:12'!
new
	^ self error: 'SemiGroup needs a set and an operation !!'! !

!SemiGroup class methodsFor: 'as yet unclassified' stamp: 'PK 4/16/2002 11:55'!
new: aSet with: anOperation

	^ super new initialize: aSet with: anOperation
! !

!SemiGroup class methodsFor: 'as yet unclassified' stamp: 'PK 4/8/2002 02:34'!
new: aSet withInst: anOperation

	^ super new initialize: aSet withInst: anOperation
! !


!GroupZn class methodsFor: 'as yet unclassified' stamp: 'PK 5/13/2002 01:50'!
new

	^ self error: 'I need a modulus !!' ! !

!GroupZn class methodsFor: 'as yet unclassified' stamp: 'PK 5/11/2002 15:45'!
new: aSet

	| TAddition |
	(aSet isfinite) ifFalse: [ ^ self error: 'Group Zn needs a finite set' ].
	TAddition := AdditionInZn new: aSet with: (aSet numberOfElements).
	^ super new: aSet withInst: TAddition.
! !


!GroupZnStar class methodsFor: 'as yet unclassified' stamp: 'PK 5/13/2002 01:51'!
new

	^ self error: 'I need a modulus!!'

! !

!GroupZnStar class methodsFor: 'as yet unclassified' stamp: 'PK 5/13/2002 01:52'!
new: anEn

	| TMultiplication TSet |
	(anEn isInteger) ifFalse: [ ^ self error: 'Group ZnStar needs integral N.' ].
	TSet := (SetZnStar new: anEn).
	TMultiplication := MultiplicationInZn new: TSet with: anEn.
	^ super new: TSet withInst: TMultiplication.
! !


!GroupRSA class methodsFor: 'as yet unclassified' stamp: 'PK 5/13/2002 01:53'!
new

	^ self error: 'I need two primes !!'
! !

!GroupRSA class methodsFor: 'as yet unclassified' stamp: 'PK 5/13/2002 01:53'!
new: anEn

	^ self error: 'I need two primes !!'
! !

!GroupRSA class methodsFor: 'as yet unclassified' stamp: 'PK 5/13/2002 01:58'!
p: aPi q: aQue

	" Should test the primality of aPi and aQue "
	^ (super new: aPi*aQue) initialize: aPi and: aQue.

! !


!SequenceableCollection methodsFor: 'converting' stamp: 'PK 5/12/2002 20:34'!
asAdditiveGroupZn
" Converts the set (sequenceable collection) to an additive group Zn, where n = number of elements of the set."

	^ GroupZn new: (self asMappingOfSet)
! !

!SequenceableCollection methodsFor: 'converting' stamp: 'PK 5/12/2002 20:33'!
asMappingOfSet
" Converts the set (resp. any sequenceable collection) to a MappingOfSet via UniversalFiniteSetMapping."

	^ UniversalFiniteSetMapping new: self! !


!SetNP methodsFor: 'mapping' stamp: 'PK 5/12/2002 20:45'!
domain

	^ nil! !

!SetNP methodsFor: 'mapping' stamp: 'PK 5/12/2002 20:46'!
elementIndex: anElement

	((anElement isInteger) and: [ anElement > 0 ])
		ifTrue: [ ^ anElement ]
		ifFalse: [ ^ self error: 'Element is not a positive integer.' ]

! !

!SetNP methodsFor: 'mapping' stamp: 'PK 5/12/2002 20:47'!
elementName: anIndex

	((anIndex isInteger) and: [ anIndex > 0])
		ifTrue: [ ^ anIndex ]
		ifFalse: [ ^ self error: 'Index is not a positive integer.' ]! !


!SetZ methodsFor: 'mapping' stamp: 'PK 5/12/2002 20:47'!
domain

	^ nil! !

!SetZ methodsFor: 'mapping' stamp: 'PK 5/12/2002 20:47'!
elementIndex: anElement

	(anElement isInteger)
		ifTrue: [ ^ anElement ]
		ifFalse: [ ^ self error: 'Element is not positive integer' ]

! !

!SetZ methodsFor: 'mapping' stamp: 'PK 5/12/2002 20:47'!
elementName: anIndex

	(anIndex isInteger)
		ifTrue: [ ^ anIndex ]
		ifFalse: [ ^ self error: 'Index is not an integer' ]! !


!SetZnStar methodsFor: 'mapping' stamp: 'PK 5/13/2002 00:44'!
domain

	| Z m |
	Z := Set new.
	m := self modulus.
	(1 to: m) do: [ :a |
		((m gcd: a) = 1) ifTrue: [ Z add: a ].
		].
	
	^ Z
! !

!SetZnStar methodsFor: 'mapping' stamp: 'PK 5/12/2002 20:58'!
elementIndex: anElement

	(anElement isInteger) ifFalse: [ ^ self error: 'This set contains only integers!!' ].
	(anElement between: 0 and: (self modulus - 1)) ifFalse: [ ^ self error: 'Elements in this set are in range 0..modulus-1,' ].
	((anElement gcd: (self modulus)) > 1) ifTrue: [ ^ self error: 'Element is not coprime to my modulus.' ].
	^ anElement.
! !

!SetZnStar methodsFor: 'mapping' stamp: 'PK 5/12/2002 20:58'!
elementName: anIndex

	(anIndex isInteger) ifFalse: [ ^ self error: 'This set contains only integers!!' ].
	(anIndex between: 0 and: (self modulus - 1)) ifFalse: [ ^ self error: 'Indexes in this set are in range 0..modulus-1,' ].
	((anIndex gcd: (self modulus)) > 1) ifTrue: [ ^ self error: 'Index is not coprime to my modulus.' ].
	^ anIndex.
! !

!SetZnStar methodsFor: 'mapping' stamp: 'PK 5/10/2002 12:01'!
initialize: aNumber

	self modulus: aNumber.
	^ self! !

!SetZnStar methodsFor: 'mapping' stamp: 'PK 5/13/2002 00:36'!
isenumerable

	^ false
! !

!SetZnStar methodsFor: 'mapping' stamp: 'PK 5/10/2002 12:05'!
isfinite

	^ true
! !

!SetZnStar methodsFor: 'mapping' stamp: 'PK 5/10/2002 12:02'!
modulus

	^ modulus
! !

!SetZnStar methodsFor: 'mapping' stamp: 'PK 5/10/2002 12:02'!
modulus: aModulus

	^ modulus := aModulus.
! !

!SetZnStar methodsFor: 'mapping' stamp: 'PK 5/13/2002 00:11'!
numberOfElements
" This set contains Phi(n) elements, but Phi is difficult to calculate, so in the case n is too large, we return our modulus-1 (not a bad guess, it works if it's a prime) "

	| Phi x z |

	(self modulus > 1000000) ifTrue: [ ^ self modulus-1 ].
	x := modulus.
	z := 2.
	Phi := 1.
	[z*z <= x] whileTrue: [
		(x \\ z = 0) ifTrue: [ 
			Phi := Phi * (z-1).
			x := x // z.
			[x \\ z = 0] whileTrue: [
				Phi := Phi * z. 
				x := x // z.
				].
			].
		z := z + 1.
		].
	(x > 1) ifTrue: [ Phi := Phi * (x-1) ].
	^ Phi
! !


!SetZnStar class methodsFor: 'as yet unclassified' stamp: 'PK 5/10/2002 11:56'!
new: modulus

	^ super new initialize: modulus! !


!UniversalFiniteSetMapping methodsFor: 'mapping' stamp: 'PK 5/12/2002 20:44'!
domain

	^ self mySet
! !

!UniversalFiniteSetMapping methodsFor: 'mapping' stamp: 'PK 5/12/2002 20:44'!
elementIndex: anElement

	|z|	
	z := myset indexOf: anElement ifAbsent: [ ^ self error: 'No such element in this set !!' ].
	^ (z-1).! !

!UniversalFiniteSetMapping methodsFor: 'mapping' stamp: 'PK 4/16/2002 11:46'!
elementName: anIndex

	^ myset at: (anIndex+1) ifAbsent: [ ^ self error: 'No such index in this set !!' ]! !

!UniversalFiniteSetMapping methodsFor: 'mapping' stamp: 'PK 4/16/2002 12:13'!
initialize: aSet

	self mySet: aSet.
	^ self! !

!UniversalFiniteSetMapping methodsFor: 'mapping' stamp: 'PK 5/13/2002 00:36'!
isenumerable

	^ true
! !

!UniversalFiniteSetMapping methodsFor: 'mapping' stamp: 'PK 4/16/2002 11:39'!
mySet

	^ myset! !

!UniversalFiniteSetMapping methodsFor: 'mapping' stamp: 'PK 4/16/2002 11:38'!
mySet: aSet

	^ myset := aSet! !


!UniversalFiniteSetMapping class methodsFor: 'as yet unclassified' stamp: 'PK 5/12/2002 20:41'!
new

	^ self error: 'I need a set!!'
! !

!UniversalFiniteSetMapping class methodsFor: 'as yet unclassified' stamp: 'PK 5/12/2002 20:43'!
new: aSet
" Creates a trivial mapping between aSet and interval 0..|aSet|-1 "

	(aSet isSequenceable) ifFalse: [ ^ self error: 'I need a sequenceable structure!!' ].
	^ super new initialize: aSet! !


!SemiGroup reorganize!
('private' addition: basicset: initialize:withInst: multiplicativeTable)
('as yet unclassified' operateOn:and:)
('accessing' addition basicset initialize:with: invert: leftInvert: leftNeutral neutral raiseElement:toPower: rightInvert: rightNeutral)
!


!RangedBinaryOperation reorganize!
('private' range range:)
('real methods' isCommutative isRealElementLeftNeutral: isRealElementRightNeutral: realInvert: realLeftInvert: realLeftNeutral realNeutral realRightInvert: realRightNeutral)
!


!BinaryOperation reorganize!
('private' map: mapping mapping: unmap:)
('as yet unclassified' initializeMapping: invert: isElement:inverseOf: isElement:leftInverseOf: isElement:rightInverseOf: isElementLeftNeutral: isElementNeutral: isElementRightNeutral: leftInvert: leftNeutral neutral operateOn:and: rightInvert: rightNeutral square:)
('real methods' isCommutative isRealElementLeftNeutral: isRealElementRightNeutral: realInvert: realLeftInvert: realLeftNeutral realNeutral realOperateOn:and: realRightInvert: realRightNeutral)
('subSet operations' invert:inASet: isClosedOnSet: isCommutativeOnSet: isElement:leftInverseOf:inSet: isElement:leftNeutralInSet: isElement:neutralInSet: isElement:rightInverseOf:inSet: isElement:rightNeutralInSet: isLeftBijectionOnSet: isRightBijectionOnSet: leftInvert:inASet: leftNeutralInSet: neutralInSet: rightInvert:inASet: rightNeutralInSet:)
!