On Mar 9, 6:39 am, casevh <cas...@gmail.com> wrote:
> [also replying to Geremy since the OP's message doesn't appear...]
>
> 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
> > > (10902610991329142436630551158108608965062811746392577675456004845499113044
> > >
> > > 30471090261099132914243663055115810860896506281174639257767545600484549911
> > > 30443047)
> > > 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
--
http://mail.python.org/mailman/listinfo/python-list
