Quick mod function ?

[dsouza123]

Cyclamen, I have coded the example you gave (with the size a single 32bit longword first).
I followed most of it, the part that still baffles me is the z = - 23 ^ (-1) mod 100 = -87 = 13.
Using z = -3^(-1) mod 10 gets the 7 but what about the -80 ?

I have been thinking about the only need the lowest digit in the case of mod 100 for the factor 23 z = - 3 ^ (-1) mod 10
I figured it ment 10 - 3 = 7 or -3 + 10 = 7

I have tried tracing through the 2^32 nary Inverse32 code but there must be something that uses a some sort of implicit wrap around/mod 2^32 in it because I plugged in 23 and got a very large number.

I have been thinking about the only need the lowest digit in the case of mod 100 for the factor 23 z = - 3 ^ (-1) mod 10
I figured it ment 10 - 3 = 7 or -3 + 10 = 7

Where you said for UNIT, full modulo not required if more that 100 - 23 = 77 is done say the full 100 mod 23 = 8 is that OK ?

I do appreciate the work you put in your replies.

[Cyclamen Persicum]

Sorry, I made a little mistake =))).
The first square is not needed. Is it 2^22 mod 23 obtained? =)))

I have been thinking about the only need the lowest digit in the case of mod 100 for the factor 23 z = - 3 ^ (-1) mod 10
I figured it ment 10 - 3 = 7 or -3 + 10 = 7


it means -3^(-1) mod 10 = -7 mod 10 = 3 (three!!!!!!!),

[alpertron]

If the modulus is 2^32, the value x = -N^(-1) mod 2^32 (where N is odd) needed for the Montgomery algorithm can be easily found without Extended Euclidean Algorithm by:

x <- 2 - N
x <- x (2 - Nx)
x <- x (2 - Nx)
x <- x (2 - Nx)
x <- x (Nx - 2)

It is assumed that all computations are done with 32-bit numbers.

[Cyclamen Persicum]

I have "discovered" a very simple method of modular reduction.
Whom is it named after?
It's much easier and almost as effective as Montgomery.
It is known that school-boy division requires n elementary Div operations
and n^2 Mult operations. "My" method eliminates the majority of Div
operations, i.e. has O(1) complexity instead O(n) relative elementary Div.

Lets find a remainder: 12345678 modulo 73.
First of all, calculate z=1000 mod 73=51 using ordinary division.
Then do as follows:

12345678
 +51=z*1
 2855678
 +102=z*2
  957678
  +459
  103578
   +51
    8678
    +408
    1086
     +51
     137 - the correct answer, but further reduction is needed.

Here we should calculate 137 mod 73 = 64 using division again.

So we need a couple elementary Div operations instead n in case of ordinary Division

[HiddenWarrior]

and what about 12345678 modulo 4321 for example? What z to take?

[Cyclamen Persicum]

Originally Posted by HiddenWarrior

and what about 12345678 modulo 4321 for example? What z to take?

10^5 mod 4321 = 0617