[SOLVED] Python squaring a square rooted number gives a different result although it should be the original number

Python squaring a square rooted number gives a different result although it should be the original number

Im working on RSA so I'm dealing with very large numbers (308 digits). In RSA a number N is the product of 2 primes p and q.

My N:

20254083928313901046078299908836135556415829454193867459405514358320313885965296062600909040071281223146837763723113350068483510086809787065437344845044248205975654791622356467691953988928774211033663314876745580293750456921795999384782277674803240671474563131823612882192899349325870727676292313218782419561

For the task I'm completing, I have been given N and am trying to find the primes p and q by implementing the method from this other post: https://crypto.stackexchange.com/questions/87417/finding-p-and-q-in-rsa-with-a-given-n-p-q10000.

When I square root N I get:

4500453746936401829977490795263804776361530154559603855210407318900755249674017838942492466443373259250056015327414929135301293865748694108450793034088448

And when I square this number I would expect to get N back, however, I get:

20254083928313899038600080147064458144896171593553283932412228091641105206147936089547530020826698707611325067918592113664216112071557998883417732874096894330570809935758528713783460134686650819864956839352000831110894044634083630533310853814832242550420262010702947392454262240042077177552422858018628042752

I'm not sure why I'm getting this result so any help would greatly be appreciated.

My code:

modulo = 20254083928313901046078299908836135556415829454193867459405514358320313885965296062600909040071281223146837763723113350068483510086809787065437344845044248205975654791622356467691953988928774211033663314876745580293750456921795999384782277674803240671474563131823612882192899349325870727676292313218782419561

sqrt = math.sqrt(modulo)
print('%i' %(sqrt))
print('%i' %(sqrt*sqrt))

Solution

There are a couple of related algorithms that can be used, and the answer in your linked question shows some of the math behind it. The one I'll show is named Fermat's factorization method. In python it's relatively easy to implement. I've implemented it myself from the Basic Method writeup in the wikipedia article.

def is_perfect_square(x: int):
    """
    If x is a perfect square then True, sqrt(x) is returned, else False, ceiling(sqrt(x)) is returned
    """
    sqrt = math.isqrt(x)
    return (True, sqrt) if sqrt ** 2 == x else (False, sqrt + 1)


def fermat_factor(n: int):
    is_square, a = is_perfect_square(n)
    b2 = a ** 2 - n
    while True:
        is_square, sqrt = is_perfect_square(b2)
        if is_square:
            break
        b2 += a + a + 1
        a += 1
    return a + sqrt, a - sqrt

This method is fast only when there is a factor close to the square root of the number you're trying to factor, and this will be true if n = p*q and p and q are relatively close together as in your problem.