1

I wrote a program for finding the two large prime nos which are used in a RSA key. It is just a ctf challenge. The problem which I am facing is that the number is being shown in power of 10 which I don't want. I want the result to be in complete number form (not in power of 10 but can be in decimal).

I already tried the Decimal library of python but I don't know why it is resulting in a wrong answer. When removed the Decimal library and it's functions it is showing the right result. However, even during the result the Decimal library is not proving the answer in complete number.

The code: 

 import math

    n = 456378902858290907415273676326459758501863587455889046415299414290812776158851091008643992243505529957417209835882169153356466939122622249355759661863573516345589069208441886191855002128064647429111920432377907516007825359999


    s=str(math.sqrt(n))
    print (s)
    s=math.ceil(s)
    print(s)

    k=(s*s)-n

    print(k)
    k=math.ceil(k)
    j=math.sqrt(k)
    print(j)

    p= (s-j)
    q= (s+j)
    print("p = " , p)
    print("q = " , q)

    i = p*q

    l = n-i
    print(l)

In this the result is 0 of l. But the p and q which I require are in huge numbers and are ( 2.136302629426752e+112 ) in power of 10 form.

SAM SAMULE
  • 35
  • 1
  • 4
  • This seems to be more about floats, but might help: [How do I suppress scientific notation in Python?](https://stackoverflow.com/questions/658763/how-do-i-suppress-scientific-notation-in-python) – glibdud Mar 29 '19 at 14:16
  • @Carcigenicate Ok I get that but the real thing to notice here is that the two nos I am getting is not prime... Is there something wrong in my logic?? Thank You for helping. – SAM SAMULE Mar 29 '19 at 14:46
  • Why would they be prime? And why would they factor your original number? – JohanL Mar 29 '19 at 14:52
  • @JohanL Actually the code up there is just a part of the whole program. In RSA encryption , two large prime numbers multiply to give n (Which is given in the above example) and we have to find those two prime numbers to go further. Well, this was out of the topic but that is why this code should actually give two prime numbers. – SAM SAMULE Mar 29 '19 at 16:43
  • You need to use integer algorithms. `math.sqrt()` etc. are designed for limited precision python floats, they aren't going to work. It looks like you are trying to factor n using something like fermat's factoring algorithm. – President James K. Polk Mar 29 '19 at 21:04
  • @SAMSAMULE Yes, but why do you think that your "algorithm" is going to produce those two primes? – JohanL Mar 29 '19 at 22:27

1 Answers1

0

I wish you luck with factoring. It is a composite and has no very small factors, nor is it trivial with Fermat. But that is beside the point.

Install gmpy2 (e.g. pip install gmpy2).

Now you can write something like:

from gmpy2 import mpz, isqrt, is_square
n = mpz('19297732862995346424713322001009')
a = isqrt(n)
while True:
  a += 1
  b2 = a*a - n
  if is_square(b2):
    break
print(n,"=",a-isqrt(b2),"*",a+isqrt(b2))

Which takes the 104-bit example input and applies Fermat's method and finds a factor quite quickly. In theory we should add a primality test first so we don't spin forever if given a prime.

DanaJ
  • 724
  • 6
  • 9