flat assembler
Message board for the users of flat assembler.

flat assembler > Heap > Calculating modular exponentiation manually

Author
Thread Post new topic Reply to topic
TmX



Joined: 02 Mar 2006
Posts: 817
Location: Jakarta, Indonesia
I once learnt this in the university, but already forgotten most of it. So I'd like to refresh my memory again.

Let's say you are asked to calculate (3 ^ 3333333) mod 100.
We can use this identity: ab mod N = (a mod N) (b mod N) mod N
Thus:
(3 ^ 3333333) mod 100
= (3 mod 100) (3^3333332 mod 100) mod 100
= 3 . (3^3333332 mod 100) mod 100
= 3 . 3 . 3 . 3 . 3 .... 3 mod 100

I'm stuck at that part. Embarassed
Are there any mathematical identities/formulas that can be used to simplify the calculation?
Post 03 Apr 2012, 06:42
View user's profile Send private message Reply with quote
YONG



Joined: 16 Mar 2005
Posts: 8000
Location: 22° 15' N | 114° 10' E
(3 ^ 3333333) mod 100 = 23 Rolling Eyes
Post 03 Apr 2012, 07:38
View user's profile Send private message Visit poster's website Reply with quote
YONG



Joined: 16 Mar 2005
Posts: 8000
Location: 22° 15' N | 114° 10' E
Note that 49^3 = 117649
So (49^3) mod 100 = 117649 mod 100 = 49
Hence (49^3n) mod 100 = (117649^n) mod 100 = (49^n) mod 100 ... (*)

(3 ^ 3333333) mod 100
= [3^(3333330+3)] mod 100
= [(3^3333330)(3^3)] mod 100
= {[(3^10)^333333][27]} mod 100
= [(59049^333333)(27)] mod 100
= [(49^333333)(27)] mod 100
= [(49^111111)(27)] mod 100
= ... | Repeatedly use (*) to reduce the number
= [(49)(27)] mod 100
= 1323 mod 100
= 23

Wink
Post 03 Apr 2012, 07:51
View user's profile Send private message Visit poster's website Reply with quote
TmX



Joined: 02 Mar 2006
Posts: 817
Location: Jakarta, Indonesia
(3 ^ 3333333) mod 100
= [3^(3333330+3)] mod 100
= [(3^3333330)(3^3)] mod 100
= {[(3^10)^333333][27]} mod 100
= [(59049^333333)(27)] mod 100

OK I understand this part. Now this is where the confusion begins:
= [(49^333333)(27)] mod 100

How do you get 49? 59049 mod 100?
So (a^b ) c mod N = (a mod N)^b c mod N?

And next:
= [(49^111111)(27)] mod 100
= ... | Repeatedly use (*) to reduce the number
= [(49)(27)] mod 100

How do you reduce [(49^111111)(27)] mod 100 into [(49)(27)] mod 100 ?
Are you implying that (a ^ b) c mod N = ac mod N?

Hmm.. this is quite hard to grasp Embarassed
Maybe you have some readable articles on this topic?
Post 03 Apr 2012, 10:21
View user's profile Send private message Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 5983
Location: Poland
Alternative solution is presented on the picture attached below:

Image
Post 03 Apr 2012, 11:48
View user's profile Send private message Visit poster's website Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 5983
Location: Poland
In case you have any problems with displaying the aforementioned picture in your browser I can give you a link to the PDF file with this solution:

http://mikhajduk.houa.org/PDF/ModularExp.pdf

BTW, I spent some time writing this in LaTeX (for better readability) and I would like to know if TmX cares about it. Wink
Post 03 Apr 2012, 18:36
View user's profile Send private message Visit poster's website Reply with quote
TmX



Joined: 02 Mar 2006
Posts: 817
Location: Jakarta, Indonesia
Hi MHajduk,

Thanks for providing another info. I've never heard of Euler's totient function before.
In general, I can understand your proof, except this part:
Image

How do you know both sides are congruent? Confused

BTW, I appreciate you wrote the proof in LaTeX, which is good for typesetting math formulas Wink
I wish this board could render LaTeX code properly.
Post 03 Apr 2012, 19:09
View user's profile Send private message Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 5983
Location: Poland
TmX wrote:
In general, I can understand your proof, except this part:
Image

How do you know both sides are congruent? Confused
You can multiply two congruences:

if

Image

and

Image

then

Image

Since we have proved that

(3^40)^83333 ≡ 1 (mod 100)

and we have a trivial congruence

3^13 ≡ 3^13 (mod 100)

so

(3^40)^83333 * 3^13 ≡ 3^13 (mod 100)

I hope this makes the whole calculation more understandable. Wink
Post 03 Apr 2012, 19:19
View user's profile Send private message Visit poster's website Reply with quote
YONG



Joined: 16 Mar 2005
Posts: 8000
Location: 22° 15' N | 114° 10' E
TmX wrote:
...
Now this is where the confusion begins:
= [(49^333333)(27)] mod 100

How do you get 49? 59049 mod 100?
So (a^b ) c mod N = (a mod N)^b c mod N?

...

How do you reduce [(49^111111)(27)] mod 100 into [(49)(27)] mod 100 ?
Are you implying that (a ^ b) c mod N = ac mod N?
Note that 59049^333333 = (59049) (59049) ... (59049)
So, (59049^333333) mod 100
= [(59049 mod 100) (59049 mod 100) ... (59049 mod 100)] mod 100
= [(49) (49) ... (49)] mod 100
= (49^333333) mod 100

...
= [(59049^333333)(27)] mod 100
= {[(59049^333333) mod 100] [27 mod 100]} mod 100
= { {[(59049 mod 100)^333333] mod 100} (27) } mod 100
= {[(49^333333) mod 100] (27)} mod 100
= {[(49 mod 100)^333333] (27)} mod 100
= [(49^333333) (27)] mod 100
= [(49^111111) (27)] mod 100 | By (*)
= [(49^37037) (27)] mod 100 | By (*)
= [(49^37035) (49^2) (27)] mod 100
= [(49^12345) (49^2) (27)] mod 100 | By (*)
= [(49^4115) (49^2) (27)] mod 100 | By (*)
= [(49^4116) (49) (27)] mod 100
= [(49^1372) (49) (27)] mod 100 | By (*)
= [(49^1371) (49^2) (27)] mod 100
= [(49^457) (49^2) (27)] mod 100 | By (*)
= [(49^459) (27)] mod 100
= [(49^153) (27)] mod 100 | By (*)
= [(49^51) (27)] mod 100 | By (*)
= [(49^17) (27)] mod 100 | By (*)
= [(49^15) (49^2) (27)] mod 100
= [(49^5) (49^2) (27)] mod 100 | By (*)
= [(49^6) (49) (27)] mod 100
= [(49^2) (49) (27)] mod 100 | By (*)
= [(49^3) (27)] mod 100
= [(49) (27)] mod 100 | By (*)
= 1323 mod 100
= 23

Wink
Post 04 Apr 2012, 04:12
View user's profile Send private message Visit poster's website Reply with quote
TmX



Joined: 02 Mar 2006
Posts: 817
Location: Jakarta, Indonesia
@MHajduk
Ah, I forgot that part. Thanks for reminding me Embarassed

@YONG
Ah thank you. Actually this is the approach I am looking for. Sorry if I make myself unclear. MHajduk's approach, while shorter, is more 'advanced'. But anyway, both approaches are interesting.


Last edited by TmX on 04 Apr 2012, 20:30; edited 1 time in total
Post 04 Apr 2012, 16:06
View user's profile Send private message Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 5983
Location: Poland
TmX wrote:
Sorry if I make myself unclear. MHajduk's approach, while shorter, is more 'advanced'. But anyway, both approaches are interesting.
That's why we formulate theorems and use them. Well chosen theorem can radically shorten your calculations. Moreover, it ensures us that when some conditions are met, the aforementioned shortcut always leads to the proper results. Wink
Post 04 Apr 2012, 18:09
View user's profile Send private message Visit poster's website Reply with quote
TmX



Joined: 02 Mar 2006
Posts: 817
Location: Jakarta, Indonesia
@MHajduk

I must be sleepy at that time Embarassed

I think YONG's approach is good for visualizing the steps, while yours is for providing formal proof, without giving too much details.

Wink
Post 04 Apr 2012, 20:54
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You can attach files in this forum
You can download files in this forum


Copyright © 1999-2018, Tomasz Grysztar.

Powered by rwasa.