Finding the Mod of a number

Stoner

Lads I could do with some help,

I cant find the Mod of a number I need it for some college stuff i.e RSA encryption,
I have some good examples etc but I'm stuck on this bit once its cracked then I'm done
This is not the actual problem its more or less a description
http://mathcircle.berkeley.edu/BMC3/rsa/node4.html

On line 6 in the solution it discusses 35 to the power or 7 by (mod 943)
this works out as 64339296875(mod 943) = 545
So its the mod of 943 that i have a problem with I'm hoping its a function on the calculator
Thanks All
Stoner

fletch

Windows Scientific Calculator has a mod function....don't know it thats of any use to you...

Stoner

Thats for that, but its not working as I expected,
8.470717376020438519907278672759e-9 LOL was what I expected, maybe i'm using it wrong,
I tried
mod 943
and
943 mod
and
64339296875 x (mod943)

but no joy,
i have a feeling its much worse then this and i sould have listened in maths class

rainbow kirby

What you're looking for is the remainder when 35^7 is divided by 943.
One way to get this without using the specific function on the calculator is (slightly more long-winded!):
(35^7)/943 = 68228310.577942735949098621420997
Take the integer part of this (68228310) and multiply this by 943.
Now work out (35^7) - (68228310*943).
Answer = 545.
Not the most efficient way of working it out, but it works here.

Esel

On e.g. Windows Scientific Calculator,

Enter 64339296875

Click Mod

Enter 943

Click =

Hope this helps.

[ The answer that is given is simply the remainder of the division of 64339296875 by 943 ]

Stoner

Lads your all beautful people, thank you

Stoner

Pherekydes

You need to brush up on your congruences. That will allow you to work out that kind of thing without a calculator.

ecksor

When I first read this thread I came to the same conclusion as Slow coach, but I'm not actually sure how congruences help to simplify this case.

In any case, that was discussed previously at http://www.boards.ie/vbulletin/showthread.php?t=161337

ecksor

Never mind me, that was a blonde moment.

All arithmetic is mod 943:

35^2 = 1225 = 282

(35^2)^2 = 282^2 = (6*47)^2 = 36 * 2209 = 36 * (2209-(2*943)) = 36 * 323 = 12 * 3 * 323 = 12 * 969 = 12 * 26 = 312

35^7 = (35^2)^2 * 35^2 * 35^2 = 282 * 312 * 35 = 6 * 47 * 3 * 8 * 13 * 35 = 6 * 1128 * 13 * 35 = 

6 * 185 * 13 * 35 = 1110 * 13 * 35 = 167 * 13 * 7 * 5 = 1169 * 13 * 5 = 226 * 13 * 5 = 2 * 113 * 13 * 5 = 1130 * 13 = 187 * 13 = 

2431 = 2431 - (2*943) = 545

charlieroot

Hmmm, couple of ways you can do this:

Left to right binary expansion.

---

35 = 5.7

=> 35^7 = 5^7.7^7

Using binary expansion of 7=(111) in base 2.

So removing the most significant bit. Going left to right on (11) square and multiply when you have a 1 square when you have a 0.

First bit (5^2)5 = A
Second bit (((5^2)5)^2)5 = (A^2)5 = 5^7 mod 943


mod'ing 943 after each operation. Do the same for 7 and multiple the two results.


Right to left binary expansion:

---

Here's some pseudo code for this method:


Power(x,n) {
r := 1
y := x
while (n > 1) {
if odd(n) then r := r*y
n := floor(n/2)
y := y*y
}
r := r*y
return(r)
}

CRT

---

You could also notice that 943=41.23 Work out the two congruences mod these primes and combine using the chinese remainder theorem.

Noel.

Stoner

thanks again, I intended to print the stuff off and learn the manual aspect off at home, however I developed futher problems, using my cal I can now do simple mod calculations and I will learn the manual method tonight as I need it for exam reasons. This problem has developed as follows

The Question
In an RSA system, the public key of a given user is e = 41, n = 3233. What is the private key of the user?

My attempt so far

Private Key = {d,n}

We know n therefore we need d

ed Mod Φn = 1

ed = 1(ModΦn)

Φn = (p-1)(q-1)

n= pq = 3233 n≠q

Factorizing 3233 we get 53x61 an 61x53 as the only non trivial answers??????

Let p = 53 and q = 61
Φn = (p-1)(q-1)
Φn = (52)(60)
Φn = 3120
ed = 1(ModΦn )
e=41 Φn = 3120
41d = 1(Mod 3120)
Private Key = {d,n}
Private Key = {d,3233}

so you see my problem, the examples in the book dont really match up and the stuff i get on the web works fine for the example that you guys helped me with before so its the 41d = 1(Mod 3120) that I have an issue with I hope that the assumptions i made in generating Φn = 3120 are correct, otherwise we are trying to solve the wrong problem.

Thanks again.

Stoner

ecksor

In an RSA system, the public key of a given user is e = 41, n = 3233. What is the private key of the user?

Um, are you sure you copied that question correctly? I'll try to point you in the right direction with your maths later.

Stoner

thats the question alright

charlieroot

The question seems to be fine - though in real life if you were given the public key of an RSA as you have been given you wouldn't be able to work out the private key as asked. The security of RSA relies on the fact that factoring n=pq is intractable. Anyway, to complete your answer you need to solve

41d = 1(Mod 3120)

In effect you're trying to find the multiplicative inverse of 41 mod 3120 ie the number which multiplied by 41 gives 1 mod 3120.

Some notation let m=3120. L = 41.

Assuming gcd(m,L) = 1 we can find u,v integers such that
mu + Lv = 1 using euclids extended algorithm. If you then mod this equation on both sides
by m you get

mu + Lv (mod m) = 1(mod m)
Lv(mod m) = 1 (mod m)

Hence v is your solution or in your notation d.

Apply Euclids extend algorithm to 3120 and 41.

3120 = 76(41) + 4 ---- (1)
41 = 10(4) + 1 ---- (2)

We want to get mu + Lv = 1 So work backwards from the bottom equation.

41 - 10(4) = 1 from (2)

4 = 3120 - 76(41) from (1)

41 - 10(3120 - 76(41)) = 1

761(41) - 10(3120) = 1

Hence d = 761

Stoner

Thanks again lads, much appreciated

StupidLikeAFox

Holy crap, ill probably be doin maths in college next year and im not lookin forward to it now!

rainbow kirby

Don't worry about it. You won't be doing that sort of thing in 1st year.

charlieroot

In fact you could go through a maths degree, do a Ph.D in maths and still not meet the above. But then you'd probably have missed the wonderful[1] world of number theory

Noel.

[1] There are varying degrees and defintions of wonderful.

Pherekydes

charlieroot wrote:

In fact you could go through a maths degree, do a Ph.D in maths and still not meet the above. But then you'd probably have missed the wonderful[1] world of number theory

Quote (from whom I can't remember):

"Mathematics is the Queen of the Arts. Number Theory is the Queen of Mathematics".

Dunno about you lot, but I love it.

ecksor

That was Gauss and he said that Mathematics was the Queen of the sciences.

Pherekydes

ecksor wrote:

That was Gauss and he said that Mathematics was the Queen of the sciences.

I stand corrected. (a first for me!)

OK, he should have said "Mathematics is the queen of the arts"

rainbow kirby

Funnily enough, I hated number theory in 2nd year...