Integer Squaring & Integer Multiplication (by product scanning) Algorithm

Sepand Haghighi & Mohammad Abassi

Cryptographic Engineering Course Seminar At Sharif University Of Technology (Winter 2017)

Instructor : Dr.Siavash Bayat-Sarmadi

Book : Cryptographic Engineering (Serdar S¨ uer Erdem, Tuˇ grul Yanık, and C ¸ etin Kaya Koc)

Download Slides (Format : PDF, Size : 1.1 MB)

Integer Multiplication

Chapter : 5

Page : 79

Fig1.Algorithm-2 Pseudocode

Fig2.Algorithm-2 Example

>>> IntegerMultiplication("1 1","1 1",Base=2)
>>> 1 0 0 1

Complexity : 3 additions, 2 data read (Inner Loop)

Integer Squaring

Book : Cryptographic Engineering (Serdar S¨ uer Erdem, Tuˇ grul Yanık, and C ¸ etin Kaya Koc)

Chapter : 5

Page : 80

Fig3.Algorithm-3 Pseudocode

Fig4.Algorithm-3 Example

• It seems this algorithm is wrong and (U,H,L) should be set to zero after each iteration and add shifted (U,H,L) outside of the loop (modified in code)

>>> IntegerSquaring("1 1","1 1",Base=2)
>>> 1 1 0 1

Fig5.Algorithm-3(Modified) Pseudocode

Fig6.Algorithm-3(Modified) Example

>>> IntegerSquaringModified("1 1",Base=2)
>>> 1 0 0 1

Complexity : 3 additions, 2 data read (Inner Loop)

Run

1. Run main.py for automatic doctest —> python main.py or python3 main.py
2. Import IntegerSquaring and IntegerMultiplication and IntegerSquaringModified from main.py :

   >>> from main import IntegerSquaring,IntegerMultiplication,IntegerSquaringModified
   >>> IntegerSquaring("1 6",Base=10)
   '3 8 6'
   >>> IntegerSquaringModified("1 6",Base=10)
   '2 5 6'
   >>> IntegerMultiplication("1 6","1 6",Base=10)
   '2 5 6'

• Enter digits with one space, for example : "31 12" in base 32