Untitled

1118 days ago by pub

WNEC Math 377
Number Theory
Prof. Caleb Shor
Spring 2010

Sage is a free open source alternative to Magma, Maple, Mathematica and Matlab. You can download and install Sage on your computer or use Sage through a browser like you are doing right now.

With Sage, we can do basic arithmetic pretty easily. To evaluate a command, put the cursor in the cell, then hold down shift and hit enter.

3+5
6*13
43^180

The underscore (_) gives the most recently output value, much like the 'Ans' command on a TI graphing calculator.

25+39

Any text entered on a line after the pound symbol (#) is a comment and is not evaluated by Sage.

factorial(100) # This command computes 100! = 100*99*98*...*3*2*1.

We can assign values to variables using the equal (=) sign.

a=23 # There is no output here because we only assigned the value.
a+51*a^2
a^100

The up and down arrows will move you from one cell to another. To delete a cell, just backspace all of the characters out of it. To insert a cell above a prior cell, hover the mouse just above the top of the cell so that a blue bar appears. Click on that blue bar to create the new cell.

# Create a new cell above this cell. Then delete this one.

Here's how we compare numbers using <, >, and ==.

2^5>5^2
10<4
3==5
b=7 # This sets b equal to 7. b==9 # This checks whether b equals 9. Sage outputs its last computation.

Sage has certain variable names reserved, like e and pi. Sage stores exact values for these quantities. For numerical approximations, use the function 'n'.

pi
n(pi) # This gives a numerical approximation of pi.
n(pi,digits=100) # "digits=" tells Sage the number of decimal digits to use for precision.
n(e,digits=1000)
cos(pi/6)

Need help with a specific function? Just type that function name and follow with a question mark.

Hit "Help" in the upper right of this page for help with finding specific functions.

plot3d?

Here is one of the examples from the end of the help file for plot3d. You should be able to move the graph around by clicking and dragging.

x, y = var('x y') plot3d(sin(pi*(x^2+y^2))/2,(x,-1,1),(y,-1,1))

Modular Arithmetic

Say we want to do arithmetic modulo n. First, we have to tell Sage that we're working mod n using the Integers() command.

R=Integers(23) # So, we'll work modulo 23.
R(5)*R(6) # This considers 5 and 6 as numbers modulo 23 and multiplies them together.
b=R(3) # Now b represents the number 3 modulo 23. So we can do arithmetic with it.
b^2
b^3 # Note: 3^3 = 27 = 1*23 + 4.
b^4 # Note: 3^4 = 81 = 3*23 + 12.
b^22 # (Fermat's Little Theorem: a^(p-1) = 1 (mod p).)
17*b # Note: 17*3 = 51 = 2*23 + 5.
b^(-1) # This is the multiplicative inverse of b modulo 23. I.e., 3 * 8 = 1 (mod 23).

Sometimes, Sage can't compute something. For instance, if we're working modulo 10 and ask for the inverse of 2, an error should appear because there is no inverse of 2 modulo 10. (Equivalently, there are no integers x,y such that 2x-10y=1 because the gcd of 2 and 10 is 2.)

M10=Integers(10) # This represents the integers modulo 10.
a=M10(2) # Setting a = 2 (mod 10).
a^(-1) # Here's the error, as we expected.
a=M10(3)
a^(-1) # 3 is relatively prime to 10, so the inverse of 3 modulo 10 exists.

Speaking of the greatest common divisor, we have the gcd command in Sage.

gcd(27,63)
gcd(1123741723849123897598127835918235,1238957789123798123598123578912357129)

The command euler_phi(n) computes the Euler phi-function of n.

n=20398208395203895
euler_phi(n)
R=Integers(n)
a=R(13513)
gcd(13513,n)
a^euler_phi(n) # Recall, if gcd(a,n)=1, then a^phi(n) = 1 (mod n).

Suppose we need an approximation of pi again.

n(pi)

Oops - we gave n a value just above, so it no longer represents the function that gives numerical approximations.

We can reset the value of any variable using the reset command. reset() will reset all defined variables. reset('n') will reset the value of a particular variable.

reset('n')
n(pi) # Now it works again. Though, of course, we've lost the value of n that we had before.

Now, for primes. Sage has primality testing built in with the is_prime() function. It also has the next_prime() function, which finds the first prime greater than or equal to a particular number.

is_prime(11)
is_prime(15)
is_prime(3889723489135981937858191)
next_prime(8)
next_prime(50)
next_prime(3598717893517893578914)

We now have all the tools we will need to perform encryption and decryption with the RSA cryptosystem!

Here are the steps.

Setup

• Pick primes $p$ and $q$.
• Let $m = p * q$.
• Pick an integer $k$ that is relatively prime to $phi(m)$. (Note: $phi(m)=(p-1)(q-1)$.)
• Solve the equation $k * u - phi(m) * v = 1$ for integers $u$ and $v$. Keep track of $u$. (Equivalently, calculate $u$, the multiplicative inverse of $k$ modulo $phi(m).$
• Publish $m$ and $k$ as public information. Keep $p$, $q$, and $u$ private.

Encryption

• Convert the message to an integer M (or list of numbers $M_1$, $M_2$, ..., $M_r$ if there are many letters in the message). One way is to let A=11, B=12, ..., Z=36 and then combine strings of letters together. For instance, "HELLO" turns into 1815222225.
• Using the recipient's public values for $m$ and $k$, evaluate $C = M^k$ modulo $m$. $C$ is the encrypted version of $M$.
• Send $C$.

Decryption

• Receive $C$.
• Compute $C^u$ modulo $m$. (We computed $u$ earlier and kept it private.)
• The result will be the original message $M$ in numeric form, which can then be converted back to letters.