Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2010-07-23 07:19:54

calccrypto
Member
Registered: 2010-03-06
Posts: 96

Weird modular multiplicative inverse

im trying to get the value of mu as shown in the stuff below, but im getting a completely different value

from http://liris.cnrs.fr/~ohasan/pprs/paillierdemo/index.html?pt1=10&pt2=21  (dont bother going there. the values change everytime)

# Select two random and distinct primes p and q of length k/2
p = 33581                                    <-- given
q = 53299                                    <-- given

# Compute n = p*q
n = 1789833719                                    <-- got this

# Compute lambda = lcm(p-1,q-1) = (p-1)*(q-1) / gcd(p-1,q-1)
lambda = 894873420                                    <-- got this

# Select a random integer g in Z*_{n^2}
g = 3082513844323755387                                    <-- given

# Compute mu = (L(g^lambda mod n^2))^-1 mod n, where L(u) = (u-1)/n                                    <-- im getting the inside stuff to be 1323971239912197708, L(u) = 739717453
mu = 1430230768

im getting mu to be 148619716. yet, the values produced work, while mine dont. what am i doing wrong?


Visit calccrypto.wikidot.com for detailed descriptions of algorithms and other crypto related stuff (not much yet, so help would be appreciated).

Offline

#2 2010-07-23 08:21:39

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Weird modular multiplicative inverse

Hi cal;

His mu is correct.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#3 2010-07-23 09:18:23

calccrypto
Member
Registered: 2010-03-06
Posts: 96

Re: Weird modular multiplicative inverse

edit: okay. i fail. i reversed the values. sorry for wasting your time

Last edited by calccrypto (2010-07-23 09:20:33)


Visit calccrypto.wikidot.com for detailed descriptions of algorithms and other crypto related stuff (not much yet, so help would be appreciated).

Offline

#4 2010-07-23 09:24:40

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Weird modular multiplicative inverse

No problem! Good to see ya!


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#5 2010-07-23 10:35:04

calccrypto
Member
Registered: 2010-03-06
Posts: 96

Re: Weird modular multiplicative inverse

Thanks


Visit calccrypto.wikidot.com for detailed descriptions of algorithms and other crypto related stuff (not much yet, so help would be appreciated).

Offline

#6 2010-07-23 11:05:24

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Weird modular multiplicative inverse

What are you working on?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#7 2010-07-23 11:38:00

calccrypto
Member
Registered: 2010-03-06
Posts: 96

Re: Weird modular multiplicative inverse

im trying to write the Paillier cryptosystem. it seems easy enough, but its not working for some reason or another


Visit calccrypto.wikidot.com for detailed descriptions of algorithms and other crypto related stuff (not much yet, so help would be appreciated).

Offline

#8 2010-07-23 12:27:05

calccrypto
Member
Registered: 2010-03-06
Posts: 96

Re: Weird modular multiplicative inverse

quick thing: what does it mean when a integer symbol has a little star next to it? i cant seem to remember and cant think of how to search for it


Visit calccrypto.wikidot.com for detailed descriptions of algorithms and other crypto related stuff (not much yet, so help would be appreciated).

Offline

#9 2010-07-23 16:21:29

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Weird modular multiplicative inverse

What's the integer symbol? You mean Z or N?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#10 2010-07-24 04:28:33

calccrypto
Member
Registered: 2010-03-06
Posts: 96

Re: Weird modular multiplicative inverse

the z, but this one also has a * next to it


Visit calccrypto.wikidot.com for detailed descriptions of algorithms and other crypto related stuff (not much yet, so help would be appreciated).

Offline

#11 2010-07-24 04:36:09

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Weird modular multiplicative inverse

I think it is a multiplicative group modulo n.

http://en.wikipedia.org/wiki/Multiplica … s_modulo_n


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#12 2010-07-24 05:11:13

calccrypto
Member
Registered: 2010-03-06
Posts: 96

Re: Weird modular multiplicative inverse

Thanks! now... how do i chose random integers from the set? i cant list out all the possible values every time. the O(n) would be ridiculous


Visit calccrypto.wikidot.com for detailed descriptions of algorithms and other crypto related stuff (not much yet, so help would be appreciated).

Offline

#13 2010-07-24 05:33:41

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Weird modular multiplicative inverse

To produce random numbers from any set is not difficult. Either you have the rule or law that creates the set or if the set is finite. You create it and store it once as an array or whatever random access container your language supports.

P = { 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47} This is the the set P such that n is prime and n<50. To draw numbers from this set, you would choose a random number from 1 to 15 and access the array element using that number:

Begin loop:

k = random(1,15): 10 - >k

P[k] is P[10]  which yields 29.

loop

Next iteration:

k = random(1,15): 3 - >k

P[k] is P[3]  which yields 5.

etc.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#14 2010-07-24 05:43:30

calccrypto
Member
Registered: 2010-03-06
Posts: 96

Re: Weird modular multiplicative inverse

yes, but what if the upper limits are large?

do you know java?
http://liris.cnrs.fr/~ohasan/pprs/paillierdemo/Paillier.java

Last edited by calccrypto (2010-07-24 05:45:19)


Visit calccrypto.wikidot.com for detailed descriptions of algorithms and other crypto related stuff (not much yet, so help would be appreciated).

Offline

#15 2010-07-24 05:54:55

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Weird modular multiplicative inverse

If k is large than you will need the rule that creates the set.

S = { 1,3,5,7,9,11,13,17,19,...1000000000001} This set contains the odd numbers [1,1000000000001]

We certainly don't want to create an array that big. But there is a rule that generates those numbers it is 2n-1 for n = 1 to 500 000 000 001.

in pseudocode:


k = random(1,500 000 000 001): 512 - >k

P[k] is P[512]  which yields 1023

Next iteration:

k = random(1,500 000 000 001): 1000000 - >k

P[k] is P[1000000]  which yields 2(1000000) - 1 = 1999999

etc


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#16 2010-07-24 06:01:48

calccrypto
Member
Registered: 2010-03-06
Posts: 96

Re: Weird modular multiplicative inverse

interesting...

i think i found another way: im going to get a random number and add 1 until the value is coprime to k


Visit calccrypto.wikidot.com for detailed descriptions of algorithms and other crypto related stuff (not much yet, so help would be appreciated).

Offline

#17 2010-07-24 06:03:59

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Weird modular multiplicative inverse

How will you test for coprime?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#18 2010-07-24 06:19:22

calccrypto
Member
Registered: 2010-03-06
Posts: 96

Re: Weird modular multiplicative inverse

i have a small function i wrote in my personal math library.

def pair_coprime(numberlist):
	for x in numberlist:
		for y in xrange(len(numberlist)):
			if x != numberlist[y]:
				out = gcd(x,numberlist[y])
				if out != 1:
					return False #Some values are not coprime
	return True #List is pairwise coprime

it could be faster, i think, but for now, its alright

i have another question:
can (a^b * c^d) mod e be done as [(a^b mod e) * (c^d mod e)] mod e? if not, whats an efficient way to do this on a computer? the exponentiation by squaring thing will still go through the second equation


Visit calccrypto.wikidot.com for detailed descriptions of algorithms and other crypto related stuff (not much yet, so help would be appreciated).

Offline

#19 2010-07-24 06:29:01

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Weird modular multiplicative inverse

Hi;

can (a^b * c^d) mod e be done as [(a^b mod e) * (c^d mod e)] mod e?

Yes.

To do it efficiently you use modular exponentiation. Described here:

http://webcache.googleusercontent.com/s … =firefox-a


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#20 2010-07-24 06:55:50

calccrypto
Member
Registered: 2010-03-06
Posts: 96

Re: Weird modular multiplicative inverse

cool! thanks


Visit calccrypto.wikidot.com for detailed descriptions of algorithms and other crypto related stuff (not much yet, so help would be appreciated).

Offline

#21 2010-07-24 07:12:05

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Weird modular multiplicative inverse

Your welcome!


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#22 2010-07-24 07:23:56

calccrypto
Member
Registered: 2010-03-06
Posts: 96

Re: Weird modular multiplicative inverse

scratch that. i messed up again

Last edited by calccrypto (2010-07-24 07:25:53)


Visit calccrypto.wikidot.com for detailed descriptions of algorithms and other crypto related stuff (not much yet, so help would be appreciated).

Offline

#23 2010-07-24 08:52:33

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Weird modular multiplicative inverse

Did you get the point of modular exponentiation? It pops up a lot in computational number theory.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#24 2010-07-24 09:44:47

calccrypto
Member
Registered: 2010-03-06
Posts: 96

Re: Weird modular multiplicative inverse

yeah, but something is just not working


Visit calccrypto.wikidot.com for detailed descriptions of algorithms and other crypto related stuff (not much yet, so help would be appreciated).

Offline

#25 2010-07-24 09:49:52

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Weird modular multiplicative inverse

Nothing in computational math ever works, you have to force it.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

Board footer

Powered by FluxBB