Posts Tagged ‘Python’

RSA Algorithm

16/01/2013

I have put together some short articles with sample code, all based on mathematical algorithms in Python.

Series One

1: A. M. Legendre, exponentiation by successive squaring.
2: Heron of Alexandria, square roots
3: Peano arithmetic
4: Zeller’s congruence
5: Factorial
6: Fibonacci numbers
7: Euclid’s GCD & prime factors
8: Eratosthenes’ Sieve and the Miller-Rabin algorithm
9: Pascal’s triangle
10: Tau using Gregory and Euler’s equations

Series Two

1. Newton’s method for nth roots.
2. Primes revisited
a) faster Miller-Rabin
b) Lucas-Lehmer number
3. A Little Number Theory
a) Ramanujan’s Highly Composite Numbers
b) Ramanujan and Hardy – roundness
c) Pythagoras – perfect numbers
d) Pythagoras – friendly numbers
4. Pi
a) Euler’s method for calculating Pi
b) Cesaro / Monte Carlo method
5. The RSA algorithm

The .zip file is here.

As a little taster, here is the code of my RSA algorithm program. You can copy and paste it and have a play and download the .zip file to read my notes in the pdf file.

# rsa.py - demo of the RSA algorithm

def main():
    n = e = d = 0
    while 1:
        print("""
    1. Set Public Key
    2. Encode
    3. Decode
    0. Quit
    Your choice? """, end = "")
        choice = int(input())
        if not choice:
            return
        if choice == 1:
            n, e, d = set_keys()
        if choice == 2:
            if not n:
                n = int(input("Public Key: "))
                e = int(input("e: "))
            encode(n, e)
        if choice == 3:
            if not d:
                n, e, d = set_keys()
            decode(d, n)

def set_keys():
    """This fuction asks for 2 primes.
    It sets a public key and an encoding number, 'e'."""
    p = int(input("p: "))
    q = int(input("q: "))
    n = p * q
    m = (p - 1) * (q - 1)
    e = get_e(m)
    print("N = ", n, "\ne = ", e)
    d = get_d(e, m)
    while d < 0:
         d += m
     return [n, e, d]

     def encode(n, e):
     """This function asks for a number and encodes it using 'n' and 'e'."""
     while 1:
         c = int(input("Number to encode: "))
         if not c:
             return
         print(pow(c, e, n))

 def decode(d, n):
     """This function asks for a number and decodes it using 'd' and 'n'."""
     while 1:
         c = int(input("Number to decode: "))
         if not c:
             return
         else:
             print(pow(c, d, n))
     
  def even(x):
     """True if x is even."""
     return x % 2 == 0

  def get_e(m):
     """Finds an e coprime with m."""
     e = 2
     while gcd(e, m) != 1:
         e += 1
     return e

 def gcd(a,b):
     """Euclid's Algorithm: Takes two integers and returns gcd."""
     while b > 0:
        a, b = b, a % b
    return a

def get_d(e, m):
    """Takes encoding number, 'e' and the value for 'm' (p-1) * (q-1).
    Returns a decoding number."""
    x = lasty = 0
    lastx = y = 1
    while m != 0:
        q = e // m
        e, m = m, e % m
        x, lastx = lastx - q*x, x
        y, lasty = lasty - q*y, y
    return lastx

if __name__ == "__main__":
    main()

You can download a .zip file with the other short articles and programs here.

Enjoy!

Download WaryPy.vdi for VirtualBox

15/04/2012

A few people have commented saying that they have tried to run RacyPy in VirtualBox and run into problems with PAE.

I’ve made a .vdi based of “WaryPy”. No PAE required.

WaryPy.vdi

MD5 sum:

15297a83b87bac54f58667f25820f076

 

My modifications to Liam Fraser’s PiShooter

24/03/2012

I am a big fan of Liam Fraser’s tutorials on YouTube. I wanted to change PiShooter so that there was an explosion when you hit the Pi. I made a few changes to Liam’s code. Becuase I am only just getting to grips with pygame, I didn’t make a class for my explosion – I just found a “quick and dirty” was to achieve my goal.

First,  I loaded up an explosion image into “boom”.

Then I added a bit to the collision detection part.

I stored the location of the shot in x1 and y1. Then, if there was a hit, I killed the Pi sprite and made a new one (so the one we hit disappears and a new one begins again at x=0. I’ve made a variable “count” and then in the main loop I blit the explosion to the screen for 20 frames. On my computer this is enough to make the explosion visible (but my laptop is pretty slow!)

antiloquax

Use pygame to make a gui.

17/03/2012

Remember that I said the main loop in our tkinter gui program was like a pygame graphics window? Well in this post I am going to use pygame to make a gui.

Here’s the code.

[Note – I will add to this post later!]

Getting started with GUIs

17/03/2012

So far all the programs I’ve done on here have been decidedly old-school and run in the command line. As I’ve mentioned before, I am learning as I go and I haven’t got very far yet with using GUIs, but I thought I’d do a post that uses the tkinter features of Python to make GUIs.

Here’s what our first GUI will look like. You can move it, resize it, minimise it and click the button (although it doesn’t do anything!).

Here’s the code.

The first line imports the tkinter modules we need. The next lines create a window and give it a size and a title. You can play around with changing these aspects, if you like. We are using a “class” within tkinter here. We’re getting into Object Oriented Programming with this little script. The line: “root = Tk()” makes a new object: an instance of the class “Tk”. We can then use some of the “methods” which that class contains. The method “title” sets the title and “geometry” defines the size.

The dot notation shows us that we are using methods. We have used this type of thing before, for instance, to raise a number to a power we said something like:

i = math.pow(2, 3)

Here the dot notation shows that we are using one of the methods defined in the math module. This one is called “pow” and it raises the first number to the power of the second. An even better example would be when we sorted a list:

mylist.sort()

Here we have created a list (“mylist”) and we use its name followed by “.sort()” to get the list-method “sort” to order our list.

Next we need a “frame” within the window, and a button. The “.grid()” method causes the layout manager to make the items we have created visible.

At the end of the code we start the main loop. This makes the window keep displaying itself on the screen and checking for any action the user might make. You may have seen similar things if you’ve had a go at pygame in which our graphics windows are controlled by a loop which runs continually until we quit the game.

I hope this makes sense! Anyway, the code itself is pretty simple. Look out for more GUI posts!

antiloquax

Java

16/03/2012

The version of the Java Development Kit you have installed in RacyPy2 is 1.7.0_02.

Firstly, I’d like to recommend Herbert Schildt’s books. I am using “Java: The Complete Reference”.

You can download the (free) first chapter of his “Java: A Beginner’s Guide” from various places online.

I am not going to write a lot about Java here – it’s better if you read the Schildt chapter. But I will mention that in Java, all programs use the Object Orientated programming model. We will get around to using this approach in Python (it’s very useful and amazingly powerful). But for simple programs, we haven’t really needed to use it.

What this means in practice is that every Java program has at least one “class”. Here’s an example:

The first four lines are a multi-line comment – we use /* to start these and */ to close them.

Next we have the command that declares the main “class”  of the program. It’s essential that this has the same name as the name of the file. It’s traditional to give this class an initial capital letter. Java is case-sensitive. So if i have called my file “Hello.java”, my class has to be called “Hello” (not “hello”). The curly braces “{” are used to group a block of code – here the contents of this class.

The next line is a single-line comment which we do by starting the line with “//”.

The next line is one you will see in almost all Java programs (I think – I am only a learner!). I’m not entirely sure what each of the commands means yet! But the important thing is that this line include the call to “main()” which all Java programs need. The next curly brace opens a new code-block – this time for what our program will actually do. What this line actually does is to invoke a class called “System” which gives us control of things like output to the screen. Within this class there is a method called “out” which does just that – outputs to the screen. The “println()” bit is just like print() in Python3 – it will print what we put inside the brackets – in this case a string enclosed in quotation marks – and add a newline. The line ends with a semi-colon because all “statements” in Java must end with a semi-colon. The lines that don’t end in semi-colons are not actually “statements” (yes – I found this a bit confusing at first, but you’ll get the hang of it!).

Then we close the curly braces that enclose the “main()” part of our code, and finally close the curly braces that end the description of our class “Hello”.

Anyway, the fun bit comes next! We have to compile our program!

Open a terminal in the directory where you saved “Hello.java”. Then type:

javac Hello.java

This compiles your program into Java bytecode. You then issue the command:

java Hello

And your program should run.

Just to make this really clear, I’ve done a few extra commands here. Typing “pwd” displays the directory we are in. Then “ls” lists the files in it. As you can see, there’s just the file “Hello,java”. Once we have run “javac Hello.java” a new file is created: “Hello.class”. When we type: “java Hello”, Java looks for a class called “Hello” and executes it, printing: “Hello World!”.

Wow, are you having fun yet!

antiloquax

C++ (and other things) in RacyPy2

16/03/2012

If you want to compile in RacyPy2, you need to load the devx file.

It is on the cd (it’s called “devx_racy_5.2.2.sfs”).

If you want to compile you’ll need to do a frugal install (this is quite simple and if you need some help, go to the Puppy Linux forum, or leave me a comment).

Then you need to put the devx file in your /mnt/home folder.

Then choose Menu > System > BootManager.

Click on the button at the top that mentions sfs files. Your devx file should appear in the list on the left. Click it and add it to the list on the right. Then reboot the machine and you will be able to compile.

There is one little problem with this – when you load the devx it will break the script that launches the Python2 IDLE when you click on this snake on the desktop.

I will sort this out for the next release. In the meantime all you need to do is download this .pet (choose open with PetGet) and it will fix the problem!

Happy compiling!

antiloquax

“Guess my Number” in Scratch

16/03/2012

I like Scratch! I was having a play with it yesterday and made this. I had to use nested if … else commands because there doesn’t seem to be away to do something like “elif”. If you know a better way to do it, please tell me!

This blog is moving …

15/03/2012

I’ve joined forces with Lobster (a Puppy Linux expert and keen Raspberryist). Our combined blog is at RaspberryPy.

I will still be posting to this blog as well, mainly because tumblr is blocked on my school’s network and I use this for teaching purposes.

Don’t forget to have a go with RacyPy2, if you haven’t already!

Hack your homework: grid multiplication

04/03/2012

Hacking your homework is not cheating. To write some code that does what you want, you’ll have to think about the maths (or whatever) very carefully. They say the best way to learn something is to teach it. When you write a program, you are teaching your computer to do something.

This program teaches the computer to use the grid method of multiplication. The key to a good maths homework hack is to get the computer to output the “working out” as well as the answer. Here’s a little screenshot of my program’s output.

As you can see, this program takes two numbers and prints out a little table representing the “grid method” way of doing multiplication and then gives you the answer.

Here’s the first part of the code:

The program starts with the usual comment lines, explaining what we are doing. Then we need to import the “math” module, because we are going to need a new mathematical function: math.pow().

I then define a function. We’ve looked at functions a bit before – by doing it this way, I can separate my numbers into hundreds, tens and units just by calling: split().

I create an empty list: grid, into which I can put the values I create. I also initialize a couple of variables, j  and k. The loop that follows is actually the most fun part of the program. I was wondering how to separate out the hundred, tens, units and so on. This is how I did it. If you can think of a simpler way, please let me know.

The loop basically takes the number and divides it by increasing powers of 10 (ie 10, 100, 1000 etc.). This is why we needed the maths module. To raise a number to a power, we need to use math.pow(). For instance if we want to square 3, we would call math.pow(3,2). Here we are using powers of 10. 10 to the power 1 is 10, squared it’s 100 and so on.

The modulus of each of these divisions gets put in “y” to start with. For instance if your number is 14, the remainder when you divide by 10 is 4 – in other words the unit part of the number. If the result is not zero, we add it to the list (we don’t want to bother with the zeros – if you multiply by 1024, for instance, you can ignore the zero for the purposes of your grid). Next I take the y away from x, because I don’t need to worry about that number any more – it’s safely stored in my list. We add one to k, so that next time through the loop we will be using the next power of 10. Finally we divide x by that next power – if the answer is zero, there’s nothing else to do and the while loop will stop.

At the end of the loop I sort the numbers in descending order and send the list “grid” back to the main part of the program.

Here’s the next part:

That’s the hardest bit done. The main part of the program gets the two numbers, sends them off to split() and stores the lists that are produced.

The next bit prints the top line of our table. I’ve made the column-width 7 – you’ll need to alter this if you are working with bigger numbers.  I use a “for” loop to print all the numbers in the first list. I have used “repr” here. This is a bit like “str” – it converts a number into a human-readable form. It also takes the method “.rjust(x)” which right-justifies the value in a column of width “x”.

The next bit is simple too – there’s a nested loop which goes through all the numbers in both lists, multiplies them and prints them. I used “col” to collect the sum of these numbers for the “totals” column and “ans” to keep a running total of that column.

The final line prints the result.

At the moment this program only deals with integers. If you have to use the grid multiplication method for floating point numbers, you could modify this program to deal with that. (Hint: 10 to the power -1 = 0.1).

happy coding!

antiloquax