finding multiplicative inverse of n
maronvomra
Can anyone please help to show how the n^-1 is 71 from this below
knapsack problem
To produce a normal knapsack sequence, take a superincreasing
increasing sequence; e.g. {1, 2, 4, 10, 20, 40}. Multiply all the
values by a number, n, modulo m. The modulus should be a number
greater than the sum of all the numbers in the sequence, for example,
110. The multiplier should have no factors in common with the modulus.
So let's choose 31. The normal knapsack sequence would be:
131 mod(110) = 31
231 mod(110) = 62
431 mod(110) = 14
1031 mod(110) = 90
2031 mod(110) = 70
4031 mod(110) = 30
So the public key is: {31, 62, 14, 90, 70, 30} and
the private key is {1, 2, 4, 10, 20.40}.
Let's try to send a message that is in binary code:
100100111100101110
The knapsack contains six weights so we need to split the message into
groups of six:
100100
111100
101110
This corresponds to three sets of weights with totals as follows
100100 = 31 + 90 = 121
111100 = 31+62+14+90 = 197
101110 = 31+14+90+70 =205
So the coded message is 121 197 205.
Now the receiver has to decode the message...
The person decoding must know the two numbers 110 and 31 (the modulus
and the multiplier). Let's call the modulus "m" and the number you
multiply by "n".
We need n-1, which is a multiplicative inverse of n mod m, i.e. n(n^
-1) = 1 mod m
In this case I have calculated n^-1 to be 71.
Thanks in advance.
maronvomra
Sorry I did some computation error.
Wolfgang Ehrhardt
<tanveer....@gmail.com> wrote:
>Hi all,
>
>Can anyone please help to show how the n^-1 is 71 from this below
>knapsack problem
[snip]
>Now the receiver has to decode the message...
>The person decoding must know the two numbers 110 and 31 (the modulus
>and the multiplier). Let's call the modulus "m" and the number you
>multiply by "n".
>We need n-1, which is a multiplicative inverse of n mod m, i.e. n(n^
>-1) = 1 mod m
>In this case I have calculated n^-1 to be 71.
>
>Thanks in advance.
That's correct,
(18:17) gp > Mod(31,110)^-1
%1 = Mod(71, 110)
but what is the question?
--
Do not use the e-mail address from the header! You can get a
valid address from http://home.netsurf.de/wolfgang.ehrhardt
(Free open source Crypto, CRC/Hash, MPArith for Pascal/Delphi)
Mok-Kong Shen
Once I saw a C code to compute the inverse of an odd number mod
2^32 but couln't locate it any more. Could someone provide a link?
Thanks,
M. K. Shen
Maaartin
> Once I saw a C code to compute the inverse of an odd number mod
> 2^32 but couln't locate it any more. Could someone provide a link?
No link, but the alg is trivial:
private boolean bit(int x, int pos) {
return ((x>>pos) & 1) != 0;
}
private int inv(int x) {
if ((x&1)==0) throw new IllegalArgumentException();
int result = 1;
for (int pos=1; pos<32; ++pos) {
if (bit(x*result, pos)) result ^= 1<<pos;
}
assert result * x == 1;
return result;
}
Thomas Pornin
> Once I saw a C code to compute the inverse of an odd number mod
> 2^32 but couln't locate it any more. Could someone provide a link?
The generic approach consists in stating that the inverse of x mod n
is x^(phi(n)-1) mod n. For n = 2^32, phi(n) = 2^31. Thus you only
have to compute x^(2^31-1) mod 2^32, which can be done with a
square-and-multiply modular exponentiation.
For n = 2^32, however, there is a much faster way. Suppose that you
have ab = 1 mod N, for some values a, b and N. This means that there
is an integer u such that ab = 1 + uN (there is no limitation on a and
b, they could be negative or greater than N).
Now let c = b(2-ab) + v(N^2) for an arbitrarily chosen value of v.
This leads to:
ac = ab(2-ab) + av(N^2)
= (1+uN)(1-uN) + av(N^2)
= 1 - u(N^2) + av(N^2)
= 1 + (av-u)(N^2)
In other words, that value of c is a modular inverse of a modulo N^2.
So the algorithm goes thus: first begin with the inverse of your odd
number x modulo 2; this is easy, that's 1. Then apply the formula
above for c five times; this will yield the inverse of x modulo 4,
16, 256, 65536, then 2^32. All computations can be performed modulo
2^32. For the first application, you know that you begin with 1, which
yields an optimized implementation.
In C this means this:
#include <stdint.h>
/*
* Invert x modulo 2^32. This function assumes that x is invertible, i.e.
* it is an odd number.
*/
uint32_t
invert_mod_t32(uint32_t x)
{
uint32_t y;
y = 2 - x;
y *= (2 - x * y);
y *= (2 - x * y);
y *= (2 - x * y);
y *= (2 - x * y);
return y;
}
which uses eight multiplications and five subtractions. Enjoy!
--Thomas Pornin
Maaartin
trivial observation that you can solve the equation
x * y = 1 mod 2**32
bitwise (starting with the lsb). I used it once for solving
y * (2*y + 1) = x
and I wonder if it could be done smarter too. It seems like getting an
expression of the form (1+uN)(1-uN) could be the way, but...
ttw...@att.net
[0,b_1,b_2,b_3....,b_k] or [.,,(b_k)-1,1]. The "reverse" continue
fraction, [b_k,b_k-1,...b_1]= c/N will yield he inverse or N-c or c as
the "other" expansion reverse. This takes about the same time as
computing a**(N-2) mod N.