need function to get cube root

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

need function to get cube root

anirvana
Hi everyone,
                  Can someone please let me have a pointer to how I may obtain a cube root of a BIGNUM, I looked up the SSLeay pages and the Openssl ducs but could not find any function that allows you to take a cube root of a BN. I've tried out BN_reciprocal() to get the value for 1/3 and then use BN_exp() to raise the BN to the power 1/3 but its not working :(. I tried obtaining the reciprocal of RSA_3 = 3 , and it seems that when I pass the len parameter as bn_num_bits(mybignum)+1 the value ends up being anything but 1/3. I'd really appreciate any help on this.
 
Thanks,
Anirban 
Reply | Threaded
Open this post in threaded view
|

Re: need function to get cube root

Bear Giles
Anirban Banerjee wrote:
> Hi everyone,
>  Can someone please let me have a pointer to how I may obtain a cube root of
> a BIGNUM,

Hopefully others will have better ideas but one possibility is to
use Newton's formula.  I'm not sure what it is with cube roots but
it's probably something like:

   y = guess;
   while (error too large)
      y = (y + x/y/y)/2

For the initial estimate it's good enough to create any number
with one third of the number of bits in the number you're taking
the cube root of.
______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
User Support Mailing List                    [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: need function to get cube root

Victor Duchovni
In reply to this post by anirvana
On Sat, Aug 06, 2005 at 05:36:52PM -0700, Anirban Banerjee wrote:

>  Can someone please let me have a pointer to how I may obtain a cube root of
> a BIGNUM

Wrong question. BIGNUMs are for high precision *integer* arithmetic,
often in a finite ring (e.g. Z/pqZ). In this context cube roots either
don't exist for most inputs (Z) or are computationally infeasible (Z/nZ).

For numbers that do have cube roots in the integer case, you can use a
half-interval search. In the discrete (Z/nZ) case you are on your own,
there are no known effective algorithms.

What problem are you trying to solve?

--
        Viktor.
______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
User Support Mailing List                    [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: need function to get cube root

Terrell
I'll toss in my 2 cents and perhaps say something either stupid or obvious.  That is that if you have a number of say 1024 bits then you can compute the cube root in 1024/3 operations where each operation in z^3.  I do not know why you need the number and I do not know if this is an acceptable cost.  




On Sat, Aug 06, 2005 at 09:26:09PM -0400, Victor Duchovni wrote:

> On Sat, Aug 06, 2005 at 05:36:52PM -0700, Anirban Banerjee wrote:
>
> >  Can someone please let me have a pointer to how I may obtain a cube root of
> > a BIGNUM
>
> Wrong question. BIGNUMs are for high precision *integer* arithmetic,
> often in a finite ring (e.g. Z/pqZ). In this context cube roots either
> don't exist for most inputs (Z) or are computationally infeasible (Z/nZ).
>
> For numbers that do have cube roots in the integer case, you can use a
> half-interval search. In the discrete (Z/nZ) case you are on your own,
> there are no known effective algorithms.
>
> What problem are you trying to solve?
>
> --
> Viktor.
> ______________________________________________________________________
> OpenSSL Project                                 http://www.openssl.org
> User Support Mailing List                    [hidden email]
> Automated List Manager                           [hidden email]
______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
User Support Mailing List                    [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: need function to get cube root

Alok-7
In reply to this post by Victor Duchovni
try using the log value?
----- Original Message -----
From: "Victor Duchovni" <[hidden email]>
To: <[hidden email]>
Sent: Sunday, August 07, 2005 6:56 AM
Subject: Re: need function to get cube root


> On Sat, Aug 06, 2005 at 05:36:52PM -0700, Anirban Banerjee wrote:
>
> >  Can someone please let me have a pointer to how I may obtain a cube
root of

> > a BIGNUM
>
> Wrong question. BIGNUMs are for high precision *integer* arithmetic,
> often in a finite ring (e.g. Z/pqZ). In this context cube roots either
> don't exist for most inputs (Z) or are computationally infeasible (Z/nZ).
>
> For numbers that do have cube roots in the integer case, you can use a
> half-interval search. In the discrete (Z/nZ) case you are on your own,
> there are no known effective algorithms.
>
> What problem are you trying to solve?
>
> --
> Viktor.
> ______________________________________________________________________
> OpenSSL Project                                 http://www.openssl.org
> User Support Mailing List                    [hidden email]
> Automated List Manager                           [hidden email]
>



______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
User Support Mailing List                    [hidden email]
Automated List Manager                           [hidden email]