2

This code is a simple implementation of Fermat's Prime Factor. When I enter random 13, 14 15 digit integer to find the factor, depends on the input value, it produces the wrong result.

unit tested with product of two prime numbers of (7919) and prime numbers under 10000. It seems working well. However, when I tried with large integer of 13, 14, 15 digit numbers, depend on the input value, it produces wrong result.

    def Prime_Factor(target):
        a = int(math.sqrt(target))
        b= a
        while((a+b) <= target): 
            a = a + 1
            b = math.sqrt(a**2 - target)
            if((b % 1) == 0):
                b = int(b)
                print('a = ', a, ', b = ',b)
                print('(a+b) = ,', (a+b), ', (a-b) = ', (a-b))
                print('(a+b) * (a-b) = ', (a+b)*(a-b), end='')
                if((a+b)*(a-b) == target):
                    print('   No Error Detected \n\n')
                else:
                    print('  <> !=' , target, '  ERROR ********   \n\n')
                    exit
                return

     import math
     Prime_Factor(9484756478341)

> Python 3.7.3 (default, Mar 27 2019, 17:13:21) [MSC v.1915 64 bit (AMD64)]
> Type "copyright", "credits" or "license" for more information.

> IPython 7.4.0 -- An enhanced Interactive Python.

> runfile('C:/Users/Paul/.spyder-py3/temp.py', wdir='C:/Users/Paul/.spyder- py3')
> a =  68579938 , b =  68510752
> (a+b) = , 137090690 , (a-b) =  69186
> (a+b) * (a-b) =  9484756478340  <> != 9484756478341   ERROR ********
blackbrandt
  • 2,010
  • 1
  • 15
  • 32
Bumki
  • 21
  • 2
  • 2
    TL;DR rounding errors on big numbers ex `b = math.sqrt(a**2 - target)`. – Jean-François Fabre Jul 15 '19 at 12:37
  • See [this](https://stackoverflow.com/questions/588004/is-floating-point-math-broken) answer for more details. – 0x5453 Jul 15 '19 at 12:39
  • perhaps you may want to use an integer approximation of square root, e.g. [`flyingcircus.base.isqrt()`](https://bitbucket.org/norok2/flyingcircus/src/b3ee0e06828375b78edcbc197040e0482372d324/flyingcircus/base.py#lines-2829) from [FlyingCircus](https://pypi.org/project/flyingcircus/). – norok2 Jul 15 '19 at 12:41
  • reminds me of those fake counter-examples for last Fermat's theorem: https://planetmath.org/falsecounterexamplestofermatslasttheorem – Jean-François Fabre Jul 15 '19 at 12:45

1 Answers1

0

Thank you everyone for the valuable comment. I've look into and found a few big integer packages for python such as gmpy2 etc. Death by truncation, indeed. Thank you for your help. cheers!

Bumki
  • 21
  • 2