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

Publication Date: 2010-Dec-15

## 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...**