Η διείσδυση των υπολογιστών, τόσο στα σπίτια μας, όσο και κυρίως στις επιχειρήσεις, κατά τα τελευταία χρόνια, καθώς επίσης και ο συνεχώς αυξανόμενος ρυθμός χρήσης του διαδικτύου, έχουν καταστήσει την ανάγκη για ασφαλείς ηλεκτρονικές επικοινωνίες και συναλλαγές κάτι παραπάνω από επιτακτική. Ένα από τα κυρίαρχα, σήμερα, συστήματα ασφαλούς ανταλλαγής δεδομένων είναι ο αλγόριθμος RSA, η ασφάλεια του οποίου βασίζεται στο γεγονός ότι είναι πολύ δύσκολο να παραγοντοποιήσουμε έναν «μεγάλο» αριθμό στους πρώτους παράγοντές του. Ο RSA αλγόριθμος θεωρείται αρκετά ασφαλής, αν βέβαια χρησιμοποιούμε κατάλληλο, για τα σημερινά δεδομένα, μέγεθος κλειδιού. Παρόλα αυτά, σε περίπτωση που βρεθεί κάποιος αποδοτικός αλγόριθμος που να μπορεί σε «λογικό» χρόνο να παραγοντοποιήσει οποιονδήποτε μεγάλο ακέραιο, τότε αυτομάτως η ασφάλεια του αλγορίθμου αυτού έχει παραβιαστεί και θα πρέπει να στραφούμε σε εναλλακτικές μεθόδους προστασίας της πληροφορίας. Ο πιο αποδοτικός σήμερα αλγόριθμος παραγοντοποίησης μεγάλων ακεραίων είναι ο Number Field Sieve. Η έρευνα που έχει γίνει πάνω σε αυτόν τον αλγόριθμο, έχει οδηγήσει σε σημαντική πρόοδο και έχει καταστήσει, πλέον, εφικτή την παραγοντοποίηση ακεραίων που υπό άλλες προϋποθέσεις θα απαιτούσε χιλιάδες χρόνια από cpu time σε supercomputers. Αν και ακόμη και σήμερα υπάρχουν αρκετά σημεία που θα μπορούσαν να βελτιωθούν στον αλγόριθμο, κάνοντάς τον ακόμη πιο αποδοτικό, ωστόσο η πολυπλοκότητά του αποτρέπει αρκετούς να ασχοληθούν με την βελτίωσή του. Με την εργασία αυτή θα προσπαθήσουμε αρχικά να διασαφηνίσουμε όλες τις πληροφορίες που απαιτούνται για την σωστή κατανόηση της λειτουργίας του αλγορίθμου. Θα γίνει λεπτομερής περιγραφή των διαφόρων βημάτων του αλγορίθμου και θα δοθεί αναλυτικό παράδειγμα παραγοντοποίησης. Τέλος, θα παρουσιαστεί η παράλληλη υλοποίησή του αλγορίθμου, η οποία μπορεί να εκτελεστεί τόσο σε supercomputer, όσο και σε cluster υπολογιστών που επικοινωνούν μεταξύ τους με χρήση του MPI. / The recent advances in computer science, in combination with the proliferation of computers in home and businesses and the explosive growth rate of the internet transactions, have increased the needs for secure electronic communications. One of the dominant systems of secure data transactions is the RSA algorithm. RSA’ s security relies on the fact that it is computationally difficult to factor a “large” integer into its component prime integers. RSA is considered secure as long as we use proper key length. However, if an efficient algorithm is developed that can factor any arbitrarily large integer in a “reasonable” amount of time, then the whole security of the algorithm will be broken, and we will have to use alternative methods to secure our systems. Today, the fastest known method for factoring large integers is the General Number Field Sieve algorithm. Research and development of the algorithm has enabled the factorization of integers that were once thought to require thousands of years of CPU time to accomplish. While there are still many possible optimizations that could increase the algorithm’s efficiency, however the complexity of the algorithm prevents many researchers from attempting to improve it. In this master thesis we present the information needed to understand the principles upon which the algorithm is based. The discrete steps of the algorithm are described in full detail, as well as a detailed factorization example, in order to enlighten the way each step works. Finally a parallel implementation is presented, able to be executed on a supercomputer or a computer cluster, with the use of MPI.

Thesis (MA) -- Stellenbosch University, 1976. / No Abstract Available

Made available in DSpace on 2016-04-27T16:58:48Z (GMT). No. of bitstreams: 1 Daniela Milaneze Rodrigues.pdf: 6569340 bytes, checksum: e50963d2dd92e9ebd4ba8aa9d8e06d24 (MD5) Previous issue date: 2008-11-18 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / The aim of this research was to investigate the third year of high school students´ comprehension of the concept of variable. For its development, it was used a theoretical framework called 3UV model formulated by researchers Trigueros e Ursini (2001). The model involves a decomposition of the concept of variable in its three main uses in elementary algebra unknown, general number and related variables, that is, variables in functional relationship and the essential abilities to comprehend each of them to acquire the concept of variable. This theoretical framework was used as guideline in the design of a questionnaire with 22 items, in which the three uses of variable were used. The questions demanded the capabilities of symbolization, manipulation and interpretation from the students related to the three uses of variable, jointly with the mobilization of the abilities that the 3UV model suggests. According to data collected, through the questionnaire and the interviews, which were realized after the application of the first, it was noticed that the students didn t show difficulties to interpret, symbolize and manipulate the variable as unknown. On the other hand, the comprehension of the variable as a general number and as related variables showed gaps related directly to the lack of mobilization of some abilities of manipulation and interpretation present in the 3UV model as needed abilities to the comprehension of the concept. Thus, this investigation helped to point up the difficulties of the students to deal with problems related to concept of variable and to indicate the abilities that should be better worked, in the teaching process of the concept of variable, to provide its comprehension / A presente pesquisa teve como objetivo investigar a compreensão de alunos do terceiro ano do Ensino Médio a respeito do conceito de variável. Para o seu desenvolvimento, foi utilizada uma ferramenta teórico-metodológica denominada modelo 3UV, elaborada pelas pesquisadoras Trigueros e Ursini (2001). Tal modelo apresenta uma decomposição do conceito de variável em seus três principais usos em álgebra elementar - incógnita, número genérico e variáveis relacionadas, ou variáveis em relação funcional e as habilidades essenciais à compreensão de cada um deles para a aquisição do conceito de variável. Essa ferramenta serviu como guia na elaboração de um questionário contendo 22 itens, envolvendo o emprego dos três usos da variável. As questões formuladas exigiram as capacidades de simbolização, manipulação e interpretação dos alunos relativas à variável em seus três usos, juntamente com a mobilização das habilidades sugeridas no modelo 3UV. Com base nos dados coletados, por meio do questionário e das entrevistas realizadas após sua aplicação, observou-se que os estudantes não apresentaram dificuldades em interpretar, simbolizar e manipular a variável como incógnita. Por outro lado, a compreensão da variável como número genérico e em relação funcional demonstrou lacunas, as quais estão diretamente relacionadas à falta de explicitação de algumas das habilidades específicas de manipulação e de interpretação apresentadas no modelo 3UV como necessárias à compreensão do conceito. Dessa forma, tal investigação possibilitou o apontamento de dificuldades dos alunos ao lidar com problemas em que o conceito de variável fazia-se presente, indicando, para o desenvolvimento de futuras pesquisas, as habilidades que deveriam ser melhor exploradas no processo de ensino para favorecer sua compreensão

Made available in DSpace on 2016-04-27T16:58:55Z (GMT). No. of bitstreams: 1 Rosania Maria da Silva.pdf: 1668777 bytes, checksum: 69484135dcc7276b463fc0748a8ce902 (MD5) Previous issue date: 2009-05-22 / Secretaria da Educação do Estado de São Paulo / This report refers to a case study that aimed to check the understanding and usage of the variable for students of eighth grade, in questions that involving their symbolization, interpretation and manipulation. Thus, we used a tool called the theoretical and methodological the three uses of variable model (3UV), presented by Trigueros and Ursini (2001). This model relates the skills necessary to understanding the three main uses of the variable in school algebra: unknown number, general number and variables in functional relationship. As a methodological tool it was used to design a questionnaire to identify the meanings and uses of the variable by seventeen students of a public school in the city of São Paulo. Besides the application of the questionnaire, which was attended by an observer, were used in audio recordings and semi-structured interviews as tools for collecting information. The set of data was analyzed taking as references the Model 3UV and aspects that, according Caraça (1954) summarize the concept of variable: the symbolic and substantial. The results show the difficulty of symbolization, especially when it should be variable of roles in general number or functional relationship. The interpretation, these students, when questioned, citing the variable as a representative of any values, but not always referring to all that it represents, but also its coefficient. In procedures for manipulation, indicating a lack of interpretation of the variable in algebraic sentences, showing the predominance of the use of algorithms for the resolution and lack of understanding of the solutions obtained, even when used correctly. The results also show that the symbolic and substantive issues stand out, separately, depending on what the question requires / Este relatório se refere a um estudo de caso que teve por objetivo verificar a compreensão e os usos da variável por alunos de oitava série, em questões que envolvem sua simbolização, interpretação e manipulação. Para tal, foi utilizada uma ferramenta teórico-metodológica denominada Modelo dos três usos da variável (3UV), apresentada por Trigueros e Ursini (2001). Tal modelo relaciona as habilidades necessárias ao entendimento dos três principais usos da variável na álgebra escolar: incógnita, número genérico e variáveis em relação funcional. Como ferramenta metodológica foi utilizado na elaboração de um questionário para identificar os significados e usos da variável por dezessete alunos de uma escola da rede estadual da grande São Paulo. Além da aplicação do questionário, que contou com a presença de um observador, foram utilizadas gravações em áudio e entrevistas semi-estruturadas como instrumentos de coleta de informações. O conjunto de dados obtido foi analisado tomando como referências o Modelo 3UV e os aspectos que, segundo Caraça (1954) sintetizam o conceito de variável: o simbólico e o substancial. Os resultados mostram a dificuldade de simbolização, principalmente quando deve ser por variáveis nos papéis de número genérico ou em relacionamento funcional. Quanto à interpretação, esses alunos, quando questionados, citam a variável como representante de quaisquer valores, porém, nem sempre se referindo ao conjunto que ela representa, mas também ao seu coeficiente. Em procedimentos de manipulação, indicam a falta de interpretação da variável nas sentenças algébricas, mostrando o predomínio do uso de algoritmos para a resolução e a falta de entendimento das soluções obtidas, mesmo quando foram utilizados corretamente. Os resultados também apontam que os aspectos simbólico e substancial se destacam, separadamente, dependendo do que requer a questão

Πολλά κρυπτογραφικά σχήματα δημόσιου κλειδιού βασίζονται στο γεγονός ότι είναι υπολογιστικά δύσκολο να παραγοντοποιήσουμε μεγάλους ακέραιους αριθμούς. Ο ταχύτερος, και ταυτόχρονα πολυπλοκότερος, κλασσικός αλγόριθμος που είναι γνωστός μέχρι σήμερα για την παραγοντοποίηση ακεραίων μήκους άνω των 110 δεκαδικών ψηφίων είναι ο General Number Field Sieve (GNFS). Ο αλγόριθμος αυτός είναι ο καρπός πολλών ετών έρευνας, κατά τη διάρκεια της οποίας παράγονταν ολοένα και ταχύτεροι αλγόριθμοι για να καταλήξουμε μέχρι στιγμής στον αλγόριθμο GNFS. Πρωταρχικός σκοπός της παρούσης μεταπτυχιακής εργασίας είναι η παρουσίαση του θεωρητικού μαθηματικού υπόβαθρου πάνω στο οποίο βασίζεται ο GNFS καθώς και η ακολουθιακή υλοποίηση της βασικής εκδοχής του αλγορίθμου. Ως γλώσσα υλοποίησης επιλέχθηκε η C++. Η υλοποίηση έγινε σε συνεργασία με τον συμφοιτητή μου και αγαπητό φίλο Χρήστο Μπακογιάννη, όπου στα πλαίσια της μεταπτυχιακής του εργασίας πραγματοποιήθηκε η μεταφορά της ακολουθιακής υλοποίησης του αλγορίθμου σε παράλληλο κατανεμημένο περιβάλλον χρησιμοποιώντας το Message Passing Interface (MPI). Ο πηγαίος κώδικας της υλοποίησης καθώς και σχετικές πληροφορίες υπάρχουν online στη σελίδα http://kmgnfs.cti.gr. Σημειώνεται πως για την ευκολότερη και απρόσκοπτη ανάγνωση της εργασίας αυτής, ο αναγνώστης θα πρέπει να έχει ένα βαθμό εξοικείωσης με βασικές έννοιες της θεωρίας αριθμών, της αλγεβρικής θεωρίας αριθμών και της γραμμικής άλγεβρας. / Many public-key cryptosystems build their security on our inability to factor very large integers. The General Number Field Sieve (GNFS) is the most efficient, and at the same time most complex, classical known algorithm for factoring integers larger than 110 digits. This algorithm is the result of many years of research, during which, faster and faster algorithms were developed finally winding up to the development of the GNFS. The main purpose of this master thesis is the presentation of the mathematical ideas, on which the GNFS was developed, as well as a sequential implementation of the basic version of the algorithm. C++ was the language of choice. The implementation took place in collaboration with my colleague and dear friend Christos Bakogiannis, where as part of his master thesis, a distributed implementation of the algorithm using Message Passing Interface (MPI) was also developed. The source code of the implementations is publicly available and can be found online at http://kmgnfs.cti.gr. It is presumed that the reader is familiar with basic concepts of number theory, algebraic number theory and linear algebra.

This work deals with factorization, a decomposition of composite numbers on prime numbers and possibilities of its parallelization. It summarizes also the best known algorithms for factoring and most popular platforms for the implementation of these algorithms on the graphics card. The main part of the thesis deals with the design and implementation of hardware acceleration current fastest algorithm on the graphics card by using the OpenCL framework. Subsequently, the work provides a comparison of speeds accelerated algorithm implemented in this work with other versions of the best known algorithms for factoring, processed serially. In conclusion, the work discussed length of RSA key needed for safe operation without the possibility of breaking in real time interval.