Our Online Store have the new products: RFID antenna board. Currently it can work with JC10M24R and JCOP4 card chips.
Compared with normal cards, the antenna board module has a smaller size and fixed holes, which is easy to integrate in the IOT(Internet Of Things) project.

how compute Phi(N) of RSA?

Algorithm School

Moderator: UNKNwYSHSA

BirdKing
Posts: 86
Joined: Wed Nov 04, 2015 7:23 am
Points :656
Contact:

how compute Phi(N) of RSA?

Post by BirdKing » Tue Nov 24, 2015 9:35 pm

hello, I have a problem about RSA. Please help me!
IN RSA,
N=P*Q
Phi(N) = (P-1)*(Q-1)

When compute standard RSA, a necessary condition is D<Phi(N).
Phi(N) = (P-1)*(Q-1) = P*Q - (P+Q) + 1
according N = P*Q, P + Q ≈ 2*(N^½)
Phi(N) = N - 2*(N^½) + 1

The problem is how to compute N^½

User avatar
horse dream
Posts: 76
Joined: Thu May 21, 2015 11:48 pm
Points :138
Contact:

Re: how compute Phi(N) of RSA?

Post by horse dream » Mon Nov 30, 2015 11:25 pm

In RSA computation,
N=P*Q
Phi(N) = (P-1)*(Q-1)

When computing RSA STD, D<Phi(N)
Phi(N) = (P-1)*(Q-1) = P*Q - (P+Q) + 1

According to N = P*Q, P + Q ≈ 2*(N^?)
Phi(N) = N - 2*(N^?) + 1

How to compute N^?:
According to X2 = [X1 + (N/X1)]/2,
The first computation, X1 takes a radom number, compute X2.
The second computation, save X1: X3 = X1, give X2 value to X1: X1 = X2, compute X2 again.
Continue computing until (X1 >= X2 and X1 >= X3) or (X1 <= X2 and X1 <= X3). And now X1 is relatively close to N^?.

e.g.
N = 15
X1 = 7, ==>> X2 = 4
X3 = 7, X1 = 4, X2 = 3
X3 = 4, X1 = 3, X2 = 3
So the value taken finally is 3.

Another example:
N = 15
X1 = 2, ==>> X2 = 4
X3 = 2, X1 = 4, X2 = 3
So the value taken finally is 4.

BirdKing
Posts: 86
Joined: Wed Nov 04, 2015 7:23 am
Points :656
Contact:

Re: how compute Phi(N) of RSA?

Post by BirdKing » Sun Dec 06, 2015 9:49 pm

Hello,
Thank you very much.
I solved the problem following your method. :lol: :lol: :lol:

Post Reply Previous topicNext topic

Who is online

Users browsing this forum: No registered users and 14 guests

JavaCard OS : Disclaimer