Spelling suggestions: "subject:"eneral number"" "subject:"feneral number""
1 |
Υλοποίηση της μεθόδου παραγοντοποίησης ακεραίων αριθμών number field sieve σε παράλληλο υπολογιστικό περιβάλλον / Implementation of the integer factorization algorithm number field sieve (NFS) on parallel computersΜπακογιάννης, Χρήστος 21 September 2010 (has links)
Η διείσδυση των υπολογιστών, τόσο στα σπίτια μας, όσο και κυρίως στις επιχειρήσεις, κατά τα τελευταία χρόνια, καθώς επίσης και ο συνεχώς αυξανόμενος ρυθμός χρήσης του διαδικτύου, έχουν καταστήσει την ανάγκη για ασφαλείς ηλεκτρονικές επικοινωνίες και συναλλαγές κάτι παραπάνω από επιτακτική. Ένα από τα κυρίαρχα, σήμερα, συστήματα ασφαλούς ανταλλαγής δεδομένων είναι ο αλγόριθμος 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.
|
2 |
Konfrontative Untersuchungen zum Plural des Substantivs im Afrikaansen und im DeutschenDu Pisani Boeke, Johanna 12 1900 (has links)
Thesis (MA) -- Stellenbosch University, 1976. / No Abstract Available
|
3 |
A compreensão de alunos, ao final do ensino médio, relativa ao conceito de variávelRodrigues, Daniela Milaneze 18 November 2008 (has links)
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
|
4 |
Diferentes usos da variável por alunos do ensino fundamentalSilva, Rosania Maria da 22 May 2009 (has links)
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
|
5 |
Η μέθοδος παραγοντοποίησης ακεραίων αριθμών number field sieve : θεωρία και υλοποίηση / The integer factorization algorithm number field sieve : theory and implementationΚαραπάνος, Νικόλαος 21 September 2010 (has links)
Πολλά κρυπτογραφικά σχήματα δημόσιου κλειδιού βασίζονται στο γεγονός ότι είναι υπολογιστικά δύσκολο να παραγοντοποιήσουμε μεγάλους ακέραιους αριθμούς. Ο ταχύτερος, και ταυτόχρονα πολυπλοκότερος, κλασσικός αλγόριθμος που είναι γνωστός μέχρι σήμερα για την παραγοντοποίηση ακεραίων μήκους άνω των 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.
|
6 |
Integer Factorization on the GPU / Integer Factorization on the GPUPodhorský, Jiří January 2014 (has links)
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.
|
Page generated in 0.0593 seconds