CODEWITHSUNDEEP
pythonpython-3.x
thomasreynolds4881
thomasreynolds4881

Reputation: 93

Exact math with big numbers in Python 3

I'm trying to implement a system for encryption similar to Shamir's Secret Sharing using Python. Essentially, I have code that will generate a list of points that can be used to find a password at the y-intercept of the gradient formed by these points. The password is a number in ASCII (using two digits per ASCII character), thus is gets to be a pretty big number with larger passwords. For example, the password ThisIsAPassword will generate a list of points that looks like this:

x    y
9556 66707086867915126140753213946756441607861037300900
4083 28502040182447127964404994111341362715565457349000
9684 67600608880657662915204624898507424633297513499300
9197 64201036847801292531159022293017356403707170463200

To be clear, these points are generated upon a randomly chosen slope (this is fine since it's the y-intercept that matters).

The problem arises in trying to make a program to decode a password. Using normal math, Python is unable to accurately find the password because of the size of the numbers. Here's the code I have:

def findYint(x,y):
    slope = (y[1] - y[0]) / (x[1] - x[0])
    yint = int(y[0] - slope * x[0])
    return yint

def asciiToString(num):
    chars = [num[i:i+3] for i in range(0, len(num), 3)]

    return ''.join(chr(int(i)) for i in chars)

def main():
    fi = open('pass.txt','r')
    x,y = [], []
    for i in fi:
        row = i.split()
        x.append(int(row[0]))
        y.append(int(row[1]))
    fi.close()
    yint = findYint(x,y)
    pword = asciiToString(str(yint))

    print(pword)

main()

Output (with the password "ThisIsAPassword"):

͉)3 ǢΜĩũć»¢ǔ¼

Typically my code will work with shorter passwords such as "pass" or "word", but the bigger numbers presumably aren't computed with the exact accuracy needed to convert them into ASCII. Any solutions for using either precise math or something else?

Also here's the code for generating points in case it's important:

import random

def encryptWord(word):
    numlist = []
    for i in range(len(word)):
        numlist.append(str(ord(word[i])).zfill(3))
    num = int("".join(numlist))
    return num

def createPoints(pwd, pts):
    yint = pwd
    gradient = pwd*random.randint(10,100)
    xvals = []
    yvals = []
    for i in range(pts):
        n = random.randint(1000,10000)
        xvals.append(n)
        yvals.append(((n) * gradient) + pwd)

    return xvals, yvals

def main():
    pword = input("Enter a password to encrypt: ")
    pword = encryptWord(pword)
    numpoints = int(input("How many points to generate? "))
    if numpoints < 2:
        numpoints = 2
    xpts, ypts = createPoints(pword, numpoints)

    fi = open("pass.txt","w")
    for i in range(len(xpts)):
        fi.write(str(xpts[i]))
        fi.write(' ')
        fi.write(str(ypts[i]))
        fi.write('\n')
    fi.close()
    print("Sent to file (pass.txt)")
main()

Upvotes: 1

Views: 1033

Answers (3)

dstromberg
dstromberg

Reputation: 7187

Fractions, and rewriting for all integer math are good.

For truly large integers, you may find yourself wanting https://pypi.org/project/gmpy/ instead of the builtin int type. I've successfully used it for testing for large primes.

Or if you really do want numbers with a decimal point, maybe try decimal.Decimal("1") - just for example.

Upvotes: 1

trincot
trincot

Reputation: 350770

It should be possible to do this only with integer-based math:

def findYint(x,y):
    return (y[0] * (x[1] - x[0]) - (y[1] - y[0]) * x[0])  // (x[1] - x[0])

This way you avoid the floating point arithmetic and the precision constraints it has.

Upvotes: 3

kaya3
kaya3

Reputation: 51093

As you may know, Python's built-in int type can handle arbitrarily large integers, but the float type which has limited precision. The only part of your code which deals with numbers that aren't ints seems to be this function:

def findYint(x,y):
    slope = (y[1] - y[0]) / (x[1] - x[0])
    yint = int(y[0] - slope * x[0])
    return yint

Here the division results in a float, even if the result would be exact as an int. Moreover, we can't safely do integer division here with the // operator, because slope will get multiplied by x[0] before the truncation is supposed to happen.

So either you need to do some algebra in order to get the same result using only ints, or you need to represent the fraction (y1 - y0) / (x1 - x0) with an exact non-integer number type instead of float. Fortunately, Python's standard library has a class named Fraction which will do what you want:

from fractions import Fraction

def findYint(x,y):
    slope = Fraction(y[1] - y[0], x[1] - x[0])
    yint = int(y[0] - slope * x[0])
    return yint

Upvotes: 4

Related Questions