Re: Calculating very large exponents in python
geremy condra
> Dear All,
>
> i am writing my crytographic scheme in python, i am just a new user to it.
> I have written the complete code, the only point i am stuck it is that i am
> using 256 exponentiation which is normal in crytography but python just
> hangs on it.
>
> g**x [where both g and x are 256 bit numbers , in decimal they are around
> 77]
>
> after reading several forums, i just come to know it can be done using
> numpy, i have installed python(x,y) has has both numpy and scipy installed
> but i am not able to make it happen.
>
> any idea which library, module, or piece of code can solve this mystery :S
>
> sorry for bad english
A couple of things:
1) if you're working with modular exponentiation, remember that pow() takes
three arguments, ie:
a = 222222222222222222222222222
b = 5555555555555555555555555555
pow(a, b, 1200)
will calculate the correct answer (768) very quickly, while
a**b % 1200
has not terminated in the time it took me to compose this
email.
2) sage has a lot of excellent tools for crypto/cryptanalysis that you
may want to take a look at.
3) not saying you don't know what you're doing, but be careful when
rolling your own cryptosystems- even very good cryptographers make
implementation mistakes!
Geremy Condra
geremy condra
> Thanks Geremy,
>
> That has been an absolute bump........... GOD i cant sit on my chair, it has
> worked even on 512 bit number and with no time..........
> superb i would say.
>
> lastly, i am using the code below to calculate Largest Prime factor of a
> number:
>
> ('''==============================================================================='''
> ''' CALCULATE HIGHEST PRIME
> FACTOR '''
>
> '''===============================================================================''')
>
> #!/usr/bin/env python
> def highest_prime_factor(n):
> if isprime(n):
> return n
> for x in xrange(2,n ** 0.5 + 1):
> if not n % x:
> return highest_prime_factor(n/x)
> def isprime(n):
> for x in xrange(2,n ** 0.5 + 1):
> if not n % x:
> return False
> return True
> if __name__ == "__main__":
> import time
> start = time.time()
> print highest_prime_factor(1238162376372637826)
> print time.time() - start
>
> the code works with a bit of delay on the number : "1238162376372637826" but
> extending it to
> (109026109913291424366305511581086089650628117463925776754560048454991130443047109026109913291424366305511581086089650628117463925776754560048454991130443047)
> makes python go crazy. Is there any way just like above, i can have it
> calculated it in no time.
>
>
> thanks for the support.
If you're just looking for the largest prime factor I would suggest using
a fermat factorization attack. In the example you gave, it returns
nearly immediately.
Geremy Condra
geremy condra
Allow me to add a very important caveat to my previous statement:
a fermat factorization is primarily useful if you know that your number
is a large semiprime, such as an RSA modulus, which I assume you
are. Otherwise, make sure and test for primality.
Geremy Con
Mark Dickinson
newsreader.]
On Mar 7, 8:40 pm, geremy condra <debat...@gmail.com> wrote:
> On Sun, Mar 7, 2010 at 1:55 PM, Fahad Ahmad <miracles...@hotmail.com> wrote:
> > Dear All,
>
> > i am writing my crytographic scheme in python, i am just a new user to it.
> > I have written the complete code, the only point i am stuck it is that i am
> > using 256 exponentiation which is normal in crytography but python just
> > hangs on it.
>
> > g**x [where both g and x are 256 bit numbers , in decimal they are around
> > 77]
No library can solve this problem. If g and x are both 256-bit
numbers then the result of g**x will have on the order of 10**79 bits,
which matches estimates of the number of particles in the universe. I
can only imagine that you actually want g**x % m for some m, in which
case three-argument pow is your friend, as Geremy pointed out.
--
Mark
casevh
On Mar 8, 11:05 am, geremy condra <debat...@gmail.com> wrote:
> On Mon, Mar 8, 2010 at 2:15 AM, Fahad Ahmad <miracles...@hotmail.com> wrote:
> > Thanks Geremy,
>
> > That has been an absolute bump........... GOD i cant sit on my chair, it has
> > worked even on 512 bit number and with no time..........
> > superb i would say.
>
> > lastly, i am using the code below to calculate Largest Prime factor of a
> > number:
>
> > print
> > ('''==============================================================================='''
> > ''' CALCULATE HIGHEST PRIME
> > FACTOR '''
>
> > '''===============================================================================''')
>
> > #!/usr/bin/env python
> > def highest_prime_factor(n):
> > if isprime(n):
> > return n
> > for x in xrange(2,n ** 0.5 + 1):
> > if not n % x:
> > return highest_prime_factor(n/x)
> > def isprime(n):
> > for x in xrange(2,n ** 0.5 + 1):
> > if not n % x:
> > return False
> > return True
> > if __name__ == "__main__":
> > import time
> > start = time.time()
> > print highest_prime_factor(1238162376372637826)
> > print time.time() - start
>
> > the code works with a bit of delay on the number : "1238162376372637826" but
> > extending it to
> > (109026109913291424366305511581086089650628117463925776754560048454991130443047109026109913291424366305511581086089650628117463925776754560048454991130443047)
> > makes python go crazy. Is there any way just like above, i can have it
> > calculated it in no time.
>
> > thanks for the support.
>
> If you're just looking for the largest prime factor I would suggest using
> a fermat factorization attack. In the example you gave, it returns
> nearly immediately.
>
> Geremy Condra- Hide quoted text -
>
> - Show quoted text -
For a Python-based solution, you might want to look at pyecm (http://
sourceforge.net/projects/pyecm/)
On a system with gmpy installed also, pyecm found the following
factors:
101, 521, 3121, 9901, 36479, 300623, 53397071018461,
1900381976777332243781
There still is a 98 digit unfactored composite:
60252507174568243758911151187828438446814447653986842279796823262165159406500174226172705680274911
Factoring this remaining composite using ECM may not be practical.
casevh
casevh
> > > makes python go crazy. Is there any way just like above, i can have it
> > > calculated it in no time.
>
> > > thanks for the support.
>
> > If you're just looking for the largest prime factor I would suggest using
> > a fermat factorization attack. In the example you gave, it returns
> > nearly immediately.
>
> > Geremy Condra- Hide quoted text -
>
> > - Show quoted text -
>
> For a Python-based solution, you might want to look at pyecm (http://
> sourceforge.net/projects/pyecm/)
>
> On a system with gmpy installed also, pyecm found the following
> factors:
>
> 101, 521, 3121, 9901, 36479, 300623, 53397071018461,
> 1900381976777332243781
>
> There still is a 98 digit unfactored composite:
>
>
> Factoring this remaining composite using ECM may not be practical.
>
>
> - Show quoted text -
After a few hours, the remaining factors are
6060517860310398033985611921721
and
9941808367425935774306988776021629111399536914790551022447994642391
casevh
Mark Dickinson
> > > makes python go crazy. Is there any way just like above, i can have it
> > > calculated it in no time.
>
> > > thanks for the support.
>
> > If you're just looking for the largest prime factor I would suggest using
> > a fermat factorization attack. In the example you gave, it returns
> > nearly immediately.
>
> > Geremy Condra- Hide quoted text -
>
> > - Show quoted text -
>
> For a Python-based solution, you might want to look at pyecm (http://
> sourceforge.net/projects/pyecm/)
>
> On a system with gmpy installed also, pyecm found the following
> factors:
>
> 101, 521, 3121, 9901, 36479, 300623, 53397071018461,
> 1900381976777332243781
>
> There still is a 98 digit unfactored composite:
>
> 602525071745682437589111511878284384468144476539868422797968232621651594065 00174226172705680274911
>
> Factoring this remaining composite using ECM may not be practical.
>
> casevh
The complete factorization is: 101 x 521 x 3121 x 9901 x 36479 x
300623 x 53397071018461 x 1900381976777332243781 x
6060517860310398033985611921721 x
9941808367425935774306988776021629111399536914790551022447994642391
It helps if you notice that the digits of the original 156-digit
number come from concatenating a 78-digit string to itself, giving an
immediate factor of 10**78 + 1. (Oops. Perhaps this was supposed to
be a secret back door to the OP's crypto scheme. I've given it away
now. :))
--
Mark
Mark Dickinson
> After a few hours, the remaining factors are
>
> 6060517860310398033985611921721
>
> and
>
> 9941808367425935774306988776021629111399536914790551022447994642391
>
> casevh
Whoops---I missed this. I'm too slow! But at least my answers agree
with yours. (Factoring 10**78+1 took around 7 seconds using GP/Pari
on a 2.5 GHz MacBook; factoring the remaining quotient n / (10**78+1)
was much quicker.)
--
Mark