Browse Prior Art Database

Novel Mechanism to efficiently calculate the nth root of a number using cryptology

IP.com Disclosure Number: IPCOM000202415D
Publication Date: 2010-Dec-15
Document File: 7 page(s) / 185K

Publishing Venue

The IP.com Prior Art Database

Abstract

Mechanism to calculate nth root of number using cryptology

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 01 of 7

Novel Mechanism to efficiently calculate the nth root of a number using cryptology

The invention aims to find the nth root of a number efficiently using modular arithmetic. It is easier to compute x power n but finding the nth root of ( x power n ) is difficult. Such functions are called one way functions.

Known solutions (http://en.wikipedia.org/wiki/Category:Root-finding

_

algorithms) are costlier (takes more

computational resources and time).

The RSA public key crypt algorithm and its properties are used as shown below to find the Nth

root of a number.

RSA Encryption:
E= ( M power e ) mod n Decryption :
M = ( E power d ) mod n n =

pq; where p and q are prime numbers.

where e and d are public and private keys, which satisfy the following properties. The keys e and d satisfy the congruence relation with φ (

pq

) / φ (n ). (φ is Euler's totient function).

(This page contains 00 pictures or other non-text object)

Where φ (

pq

) / φ (n ) = (

p

- 1) * (q - 1)


i.e.,


d.e = k . (

p-1)(q-1) + 1 where k = 1, 2, 3, …..

When ever the computing resources are available, try to construct a table as explained below.

*Generate a set of prime numbers.
*Generate 2 element combinations from the above found prime number set (NC2 elements). {p,q} *Compute p * q for each of the formed combinations.
*Compute
φ (

pq

- 1) * (q - 1) for each pair.

*find different sets of

which satisfies the following criteria.

) / φ (n ) = (

p

1


Page 02 of 7

Construct a table which contains the table in the following format.

P

Q

P * Q

The functions which provides simpler encryption and difficult to decrypt are called one way

function. For instance finding nth power of a number is easy but getting back nth root is difficult Objective : Using RSA algorithm to find the nth root:
Given : A (which is M power e) and e (e is known since the objective itself is to find eth

root)

To find : M Algorithm derivation : As per RSA algorithm :

Encryption

E = ( M power e ) mod n ---------------------------------(1)

Decryption

M = ( E power d ) mod n ----------------------------------(2)

We are provided with A (which is M power e). We need to form an n (by choosing two different

2

(This page contains 00 pictures or other non-text object)

(P -1)

*

(Q -1)

E

D


Page 03 of 7

prime numbers p and q satisfying the criteria n is greater than the value

(floor(

ed = K(p-1)(q-1) + 1 where K is an integer ----------------(2)

If we found such d and n then, do the following steps to get M (i.e., eth root of A). compute

E = A mod n = ( M power e ) mod n
then compute
(E power d ) mod n = M (Since we are making use of the properties of RSA, we get back

M as the decryption retrieve back the message) To find out such n and d

r

_digits(A) / e)). This is to make sure M is always less than n. (as we have in

RSA that m should always lesser tha n (i.e,

Search for e in both columns E & D.

If e is found in column E then use D as d in (E power d ) mod n.

If e is found in column D then use E as d and compute (E powe...