Introduction to SAGE and Object-Oriented-Programming

1.) Linux

1.1.) Console, Filemanagment

1.2.) Editor (Scite and Emacs)

Scite is a simple editor. For advanced tasks use Emacs. Emacs has a nice tutorial (available from the help menu), which teaches the basic editing skills.

2.) Introduction to SAGE

2.1.) Helloworld in Python/SAGE on the Console

Start python and enter 'print "Hello World"'

[lf@velocity:~] python
Python 2.5.1 (r251:54863, May  2 2007, 16:56:35)
[GCC 4.1.2 (Ubuntu 4.1.2-0ubuntu4)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> print "Hello World"
Hello World
    >>>

The same works for SAGE:

[lf@velocity:~] sage
----------------------------------------------------------------------
| SAGE Version 2.8.6, Release Date: 2007-10-06                       |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------

sage: print "Hello Word"
Hello Word

Compare this single line with HelloWorld in different Computer Languages

You can always start python or SAGE on the console and try out things.

2.2.) SAGE-Intro using the Notebook

Notebook (login in as cip, with password cippool, I have to start the notebook before). Go to Home and create a copy of the Worksheet.

2.3.) Things to remember:

2.4.) Why OOP?

OOP and object-oriented-design are tools to achieve better (less errors) programs. As software became bigger and more complex, there were more and more problems.

Something changed in one place caused problems in another place. This was because the early programming practise (tools and concepts) did not emphasise on modularity. Even with procedural programming there were all sorts of nasty side-effects. For example:

OOP deals with this problems by introducing new ideas and concepts: The class consists of data (called attributes) and functions (called methods). It consists of all the functionality for this class. If you change the implementation, you know where you have to look.

2.4.1.) Implementation Hiding and Encapsulation

A class has an interface to the outside. This interface should be independent of implementation details. Outside the class, everyone has to use the interface. So there are no problems with implementation changes. Consider the next example:

class Rect(object):
    def __init__(self, x1,y1, x2,y2):
        self.x1 = x1
        self.x2 = x2
        self.y1 = y1
        self.y2 = y2

    def giveArea(self):
        dx=self.x2-self.x1
        dy=self.y2-self.y1

        return dx*dy


if __name__=="__main__":
    R1=Rect(10, 10 , 110,50)
    print R1.giveArea()

The idea of OOP is that giveArea() belongs to the Rect-Class. With procedural Programming we (as the creator of the Rect-Class) have no control what a user would do with a Rect-Object. Some users would use our giveArea methods, other would access x1,x2,y1,y2 directly.
What happens, if we change our Rect-Class? 

class Rect(object):
    def __init__(self, x1,y1, x2,y2):
        self.x1 = x1
        self.y1 = y1
		
	self.width = x2-x1
	self.height= y2-y1	

    def giveArea(self):
        return self.height * self.width


if __name__=="__main__":
    R1=Rect(10, 10 , 110,50)
    print R1.giveArea()

With OOP no user would directly access x1,x2,y1,y2, only the giveArea() method and we can change our implementation, as long as the signature (arguments and return value) of giveArea() stays the same.

To support implementation hiding OOP-languages protect the attributes of classes, so that they cannot be changed from the outside. Consider this example in gp:

? K=nfinit(polcyclo(7))
? K.pol
%7 = x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
? K[1]="Boom"
%8 = "Boom"
? K.pol
%9 = "Boom"

What happens, if we continue using K? 

? nfsubfields(K)
*** nfsubfields: bug in GP (Segmentation Fault), please report

Sometimes objects should be read-only or at least the author should control what can be modified. With OOP we would define methods to read attributes (like .pol) but restrict write access.

Python has only a limited support for access control. Everything is public and there is only a kind of private attributes through attributes beginning with "__" but not ending with "__". This is merely a way to prevent name clashes between a class an its subclasses. But there is a recipe on the Python-Cookbook's Homepage which introduces public and protected attributes.

From the Python Tutorial: 'classes in Python do not put an absolute barrier between definition and user, but rather rely on the politeness of the user not to "break into the definition."'

2.4.2.) Modularity

Because a class hides its implementation, it is self-contained. Breaking a problem down to different independent classes, breaks complexity into smaller parts. Each part (the class) can be developed independently. OOP actively supports modularisation.

A new class introduces a new namespace. So there can be a giveArea() method for rectangles and triangles (Rect.giveArea() and Triangular.giveArea() ). With procedural programming there is one namespace and everything lives in this namespace (or at least in the modules namespace). For example Pari has no modules).

2.4.3.) Reusing Code through Inheritance

Define new classes, that modify the behaviour of existing classes. Reuse the code of the base-class. Only code the difference between base- and subclass. A method in a base-class can be overwritten by a sub-class. The sub-class can call the implementation of the base-class.

Create an object hierarchy, with common objects at the top providing common functions. Objects at the bottom becoming more and more specific. For example have a look at the QT-GUI-Library. Especially the Class-Chart.

An example for inheritance:

class Base(object): # new style class because we inherit object
    def __init__(self):
        self.Name= "Base"
        self.attribute= "an attribute of the Base"
        print "Base-Constructor"


    def printObj(self):
        print self.__dict__


class SubClass(Base):
    def __init__(self):
        # we have to call it the inherited constructor
        # explicitly
        # if we omit the call SubClass would not have self.attribute
        
        super(SubClass,self).__init__()
        
        # there is another way to call an inherited mathod:
        # using the Name of the Class, here Base
        #   Base.__init__(self)
        # with super() we use the Name of the SubClass
        
        self.Name= "SubClass" 
        self.anotherAttribute= "this is from the SubClass"
        print "SubClass-Constructor"


if __name__=="__main__":
    Objs= [ Base(), SubClass(), SubClass() ]

    for o in Objs:
        # instances of SubClass have also a printObj() method (from Base)
        o.printObj()


# Local Variables:
#   mode:python
# End:

SubClass inherits Base, so it posses the printObj() method, too, So does o in the last line. This is called Polymorphism.

2.4.4.) Object Relations

There are two ways to use Object that can be related: For example a rectangle has four points and a square is a rectangle. Expressed in OOP-Terms: if we have a Point-Class, the Rectangle Class can have four Point objects and the Square-Class can inherit Rectangle. 

class Point( object ):	
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def getCoordinates(self):
        return [self.x, self.y]


class Rect( object ):
    def __init__( self, Point1, Point2, Point3, Point4 ):
        self.Points = [ Point1, Point2, Point3, Point4 ]

    def getCoordinates(self):
        return [ p.getCoordinates() for p in self.Points ]
            

class Square( Rect ):
    def __init__(self, FirstPoint, length):
        Point2=Point(FirstPoint.x + length , FirstPoint.y          )
        Point3=Point(FirstPoint.x + length , FirstPoint.y + length )
        Point4=Point(FirstPoint.x          , FirstPoint.y + length )
        Point2=Point(FirstPoint.x + length , FirstPoint.y          )

        Rect.__init__(self, FirstPoint, Point2, Point3, Point4)


if __name__=="__main__":
    S=Square( Point(100,100,), 50 )
    
    for c in  S.getCoordinates():
        print c
    
# Local Variables:
#   mode:python
# End:

2.4.5.) Advantages of OOP

Everything can be achieved without OOP (in the end the program is transformed to machine code, as it is with non-OOP-languages), but OOP makes life easier.

2.5.) SAGE and OOP using file&editor

Have a look at the RSA- and ElGamalCryptoSystem in the next example: copy the code, save it to local file say crypto.sage. Then start SAGE and issue the command:

attach crypto.sage

After you save modifications to the file, you can change to SAGE an hit enter. The modification become active in SAGE. (With scite (and my configuration files) you could hit F5 and the file is executed by SAGE, the output occurs in scite's output window.) 

#!/usr/local/bin/sage

# Example for OOP, inheritance and some of Python's OOP-specialties:
# Notice:  self,  __init__,  super( ... ) 


class PublicKeyCryptoSystem(object): # we inherit object, which gives a "New-Style-Class"
    r"""Base class of a public key cryptosystem.

    This has only some tool-functions. The others (RSA and ElGamal) should inherit this
    class."""

    def __init__(self, Name="Base Class", MAX_Prime=1000000000 ):
        self.Name = Name
        # Polymorphic: createKeys is implemented in each SubClass
        self.createKeys(MAX_Prime)
        

    # giveName is defined in the Base-Class
    def giveName(self):
        return "This is the " + self.Name +"."


    # this method is overwritten in subclasses, but it has a useful function
    # subclasses should call this implementation in their encrypt() method
    def encrypt(self, receiver, msg):
        r"""Encrypt the String msg with receiver's public key.

        This method should be overwritten in sub-classes. But the
        sub-class should call this method for the type-checking-code.
        """
        # we test if receiver and self are the same type (e. g. Crypto-System)
        if type(self) != type(receiver):
            raise Exception("Cryptosystem of receiver does not match with sender!\nself is: "+str(type(self))+" while Receiver is: "+str(type(receiver)))
        return None
    # of encrypt()

    # subclasses call this:
    def normalizeMessage(self, msg):
        r"""The message is converted to all uppercase ascii Letters, dropping umlauts.
        """
        ret=''
        for m in msg:
            M=m.upper()
            # an uppercase ascii letter has value 65..90 < 100
            if ord(M) < 100:
                ret+=M
                
        return ret
    # of normalizeMessage()
    

    # subclasses call this:
    def messageToNumberList(self, msg):
        r"""The message is represented as a list of numbers < some limit.

        The limit is set in the subclasses (e.g. N for RSA)
        """
        Msg= self.normalizeMessage(msg)

        NumberList= []
        number= 0
        Mult= 1
        # n-adic representation of msg with n=100
        # ABC becomes: [ 65+100*66+100^2*67 ]
        # (ord('A') = 65 ...
        for m in Msg:
            if number + Mult*100 >= self.limit:
                NumberList.append(int(number))
                number=0
                Mult=1
                
            number+= ord(m)*Mult
            Mult *= 100
                
        NumberList.append(number)
        return NumberList
    # of messageToNumberList()


    # subclasses call this:
    def numberListToMessage(self, L):
        msg = ''
        for nr in L:
            while (nr >0):
                c= int(Mod(nr, 100))
                nr = int(nr) // 100
                msg+= chr(c)
                
        return msg
    #of numberListToMessage()
    
# end of Base-Class PublicKeyCryptoSystem
    
    

class RSACryptoSystem(PublicKeyCryptoSystem):
    r"""Implements the RSA-Cryptosystem.

    EXAMPLE:
    sage: Alice=RSACryptoSystem()
    sage: Bob=RSACryptoSystem()
    sage: code= Alice.encrypt(Bob,'Hello Bob, attack at dawn.')
    sage: Bob.decrypt(code)
    'Hello Bob, attack at dawn.'"""

    def __init__(self, MAX_Prime=1000000000):
        """Constructor of RSACryptoSystem."""

        # call the constructor of the base class, which calls createKeys() 
        super(RSACryptoSystem, self).__init__("RSA-Crypto-System", MAX_Prime )
    # of __init__()


    def createKeys(self, MAX_Prime):
        r"""Choose 2 random primes P,Q between 2 and MAX_Prime and create the
           keys according to RSA."""
        
        P= random_prime(MAX_Prime)
        Q= random_prime(MAX_Prime)
        N= P*Q

        phi= euler_phi(N)
        e= randint(2,phi-1)
        # ensure that e is invertible
        while gcd(e,phi) != 1:
            e= randint(2,phi-1)
            
        d= Mod(e,phi)^-1

        # __* are class Private Attributes
        # both attributes can only be accessed from this class
        self.__privateKey= d
        self.__publicKey = [N,e]
        self.limit = N
    # of createKeys()
    

    def getPublicKey(self):
        return self.__publicKey

    
    def encrypt(self, receiver, msg):
        """Encrypt every single character with receiver's public key."""
        
        super(RSACryptoSystem, self).encrypt(receiver, msg)

        pubKey= receiver.getPublicKey()
        
        encryptedMsg= []
        # a method of the base-class
        NumberList=self.messageToNumberList(msg)
        
        for nr in NumberList:
            # v=nr^e mod N
            v= Mod(nr, pubKey[0])^pubKey[1]
            encryptedMsg.append(int(v))

        return encryptedMsg
    # of encrypt()
    

    def decrypt(self, encryptedMsg):
        """Decrypt every single character with self's private key."""
        
        d= self.__privateKey
        N= self.__publicKey[0]
        
        msg=""
        NumberList=[]
        for v in encryptedMsg:
            # nr=v^d mod N
            nr= Mod(v, N)^d
            NumberList.append(nr)
            #msg += chr(m) # append the character with ascii value c

        # a method of the base-class
        msg= self.numberListToMessage(NumberList)
        return msg
    # of decrypt()


class ElGamalCryptoSystem(PublicKeyCryptoSystem):
    r"""Implements the El-Gamal-Crypto-System.

    EXAMPLE:
    sage: Bob=ElGamalCryptoSystem()
    sage: Alice= ElGamalCryptoSystem()
    sage: code=Bob.encrypt(Alice, 'Attack at dawn!')
    sage: Alice.decrypt(code)
    'Attack at dawn!'"""
    
    def __init__(self, MAX_Prime=1000000000):
        """Constructor of ElGamalCryptoSystem."""
        
        # call the constructor of the base class:
        super(ElGamalCryptoSystem, self).__init__("El-Gamal-Crypto-System", MAX_Prime )
    # of __init__()
    
        
    def createKeys(self, MAX_Prime):
        """Create keys according to El-Gamal."""
        
        P=1 # find prime P with P-1 has a large Prime-Factor Q
        while not (is_prime(P) and P >256) :
            # P should be bigger than 256, so we can enocde ascii character in 0...P-1
            Q= random_prime(MAX_Prime)
            P= 2*Q+1 # try to get P=2*Q+1 with P and Q prime (Sophie-Germain-prime)

        # primitive root mod P
        G= primitive_root(P)
        # random int
        a= randint(0,P-2)
        
        A= Mod(G,P)^a
        # private key=a, public key = [P,G,A]

        # __* are class Private Attributes
        # both attributes can only be accessed from this class
        self.__privateKey= a
        self.__publicKey = [P, G, A]
        self.limit= P

    def getPublicKey(self):
        return self.__publicKey
    
    
    def encrypt(self, receiver, msg):
        """Encrypt every single character with receiver's publickey."""

        super(ElGamalCryptoSystem, self).encrypt(receiver, msg)

        P,G,A= receiver.getPublicKey()
        
        encryptedMsg= []
        
        # a method of the base-class
        NumberList= self.messageToNumberList(msg)
        for nr in NumberList:
            
            b= randint(2, P-2 )
            B= Mod(G,P)^b
            c= Mod(A,P)^b * Mod(nr, P)

            # B=G^b mod P, c= (A^b * nr) mod P
            encryptedMsg.append( [B,c] )

        return encryptedMsg
    # of encrypt()
    

    def decrypt(self, encryptedMsg):
        """Decrypt every single character with self's private key."""

        
        P= self.__publicKey[0]
        NumberList= []
        
        for v in encryptedMsg:
            B=v[0]
            c=v[1]
            #  B^(P-1 - a)*c = G^(b *(( P-1) -a)) *G^(a*b) *m =
            #  G^(-ab+ b(P-1) +ab) *m= 1 *m
            nr= Mod(B, P )^(P-1 - self.__privateKey ) * Mod(c,P)

            NumberList.append(nr)

        # a method of the base-class
        return self.numberListToMessage(NumberList)
    # of decrypt()



def testCryptoSystem(classType):
    msg = "Attack at dawn!"
    
    Alice = classType()
    Bob   = classType()

    code= Alice.encrypt(Bob, msg)
    print Alice.giveName(), "\n   The coded message is:\n  ", code
    d= Bob.decrypt(code)
    
    if d != Alice.normalizeMessage(msg):
        print Bob.giveName()+" Something is wrong!"
    else:
        print d 
# of testCryptoSystem()    


# if the file itself is run (e.g. not included, imported, attached, etc.)
# __name__ is "__main__" and this Module-Test-Code is executed.
if __name__== "__main__":
    testCryptoSystem(RSACryptoSystem)
    testCryptoSystem(ElGamalCryptoSystem)
    

# Local Variables:
#   mode:python
# End:

2.6.) Further Topics in Python

nach oben

Letzte Änderung: 05.08.2009
© Lars Fischer

Valid XHTML 1.1!  Valid CSS!