This thesis represents the results of a study into using fingerprints generated according to the Rabin-Karp Algorithm, and a database LevelDB to achieve Text Search times below GREP, which is a standard command-line UNIX text search tool. Text Search is a set of algorithms that find a string of characters called a Search Pattern in a much larger string of characters in a document we call a text file. The Rabin-Karp Algorithm iterates through a text file converting character strings into fingerprints at each location. A fingerprint numerically represents a window length string of characters to the left of its location. The algorithm compares the calculated fingerprint to the Search Pattern’s fingerprint. When fingerprints are not equal, we can guarantee the corresponding strings will not match. Whereas when fingerprints are, the strings probably match. A verification process confirms matches by checking respective characters. Our application emerges after making the following major changes to the Rabin-Karp Algorithm. First, we employ a two-step technique rather than one. During step 1, the preprocessing step, we calculate and store fingerprints in a LevelDB database called an Index Database. This is our first major change unique to us. Step 2, the matching step, is our second unique change. We use the Index Database to look-up the Search Pattern’s fingerprint and gather its set of locations. Finally, we allow the pattern to be any length relative to the window length. We even created an equation to check if the difference in length is too long for the fingerprint’s number system base. We facilitated our performance experiments by first building our application and testing it against GREP for a wide range of different parameters. Our conclusions and recommendations determine that although we currently only outperform GREP in about half the cases, we identify some promising opportunities to modify some parts of our application so that we can outperform GREP in all instances. / UOIT

Användningen av automatiserade system är en vanlig lösning för att underlätta en manuell arbetsbörda inom många områden. Autolab är en prototyp av ett automatiskt laborationsrättningssystem avsett att kunna användas som ett hjälpmedel inom undervisning för att reducera arbetsbördan för lärare. Examensarbetet har inneburit att skapa och integrera ny funktionalitet till systemet. Bland annat att skapa en enklare plagiatkontroll baserad på strängmatchning för att upptäcka och förhoppningsvis förbygga fusk mellan studenters inlämnade laborationer. För att underlätta förståelsen till användare för hur Autolab fungerar skapades dokumentation över hur systemet används som både lärare och student. Efter att analyserat vad som implementerats till Autolab ges förslag på vad som kan förbättras i systemet till framtiden.

Com o surgimento da criptografia de chave pública, muito esforço foi feito para a criação de protocolos de criptografia e de assinatura que fossem comprovadamente seguros contra indivíduos maliciosos. Existem várias definições de segurança, tanto para protocolos de criptografia como para protocolos de assinatura, e também existem vários modelos de adversários, que simulam um indivíduo malicioso tentando corromper o protocolo. A família de protocolos de assinatura Rabin possui os recordes de velocidade de vericação da assinatura, chegando a ser até 100 vezes mais rápida do que o RSA. Este trabalho apresenta uma redução eficiente de segurança no modelo do oráculo aleatório para uma variante do protocolo de assinatura Rabin descrito por Bernstein, onde não é necessário o uso de nenhuma função para geração de bits pseudo-aleatórios, o que torna o protocolo mais robusto. A redução apresentada é uma redução polinomial e eficiente do problema da fatoração de inteiros para o problema de quebrar o protocolo Principal Rabin-Williams B = 0. / With the development of public-key cryptography, many efforts were made to build encryption and signature protocols that were provably secure against malicious adversaries. There are many definitions of security for encryption and signature protocols, and there are many adversary models to simulate the behaviour of a malicious adversary against a given protocol. The Rabin family of signature protocols has the speed records for verification of signature, being up to 100 times faster than RSA. This work presents a tight security proof in the random oracle model for a variant of the Rabin signature protocol presented by Bernstein, that does not require the use of pseudo-random bits, making the protocol more robust. The proof presented here is a polynomially tight reduction for the problem of integer factorization to the problem of breaking the Principal Rabin-Williams B = 0 protocol.

Com o surgimento da criptografia de chave pública, muito esforço foi feito para a criação de protocolos de criptografia e de assinatura que fossem comprovadamente seguros contra indivíduos maliciosos. Existem várias definições de segurança, tanto para protocolos de criptografia como para protocolos de assinatura, e também existem vários modelos de adversários, que simulam um indivíduo malicioso tentando corromper o protocolo. A família de protocolos de assinatura Rabin possui os recordes de velocidade de vericação da assinatura, chegando a ser até 100 vezes mais rápida do que o RSA. Este trabalho apresenta uma redução eficiente de segurança no modelo do oráculo aleatório para uma variante do protocolo de assinatura Rabin descrito por Bernstein, onde não é necessário o uso de nenhuma função para geração de bits pseudo-aleatórios, o que torna o protocolo mais robusto. A redução apresentada é uma redução polinomial e eficiente do problema da fatoração de inteiros para o problema de quebrar o protocolo Principal Rabin-Williams B = 0. / With the development of public-key cryptography, many efforts were made to build encryption and signature protocols that were provably secure against malicious adversaries. There are many definitions of security for encryption and signature protocols, and there are many adversary models to simulate the behaviour of a malicious adversary against a given protocol. The Rabin family of signature protocols has the speed records for verification of signature, being up to 100 times faster than RSA. This work presents a tight security proof in the random oracle model for a variant of the Rabin signature protocol presented by Bernstein, that does not require the use of pseudo-random bits, making the protocol more robust. The proof presented here is a polynomially tight reduction for the problem of integer factorization to the problem of breaking the Principal Rabin-Williams B = 0 protocol.

This thesis describes methods for duplicate traffic detection in computer networks. At first, it analyzes the problem of redundant traffic including the description of its origin and causes. The thesis describes on what data and what methods we are able to detect an operation as duplicate. Finally, this thesis explains design of redudant traffic detection algorithm including testing plan and results evaluation.

Esta pesquisa foi realizada com a intenção de motivar o estudo da criptografia, mostrando que a matemática e a comunicação estão presentes em diversos momentos, tanto no passado quanto no presente. Este trabalho mostra a origem da criptoanálise e toda a sua evolução dando ênfase nos mecanismos de codificação e decodificação através de exemplos práticos. Além disso, alguns métodos criptográficos são destacados como a cifra de substituição monoalfabética, a cifra de Vigenère, a criptografia RSA que é o método mais conhecido de criptografia de chave pública, as cifras de Hill, o método das transformações lineares e o método de Rabin, devido a sua grande importância para a evolução de sistemas computacionais e assinaturas digitais entre outros. Por fim, mostra-se a importância e a necessidade dos recursos criptográficos nos dias de hoje, na tentativa de impedir que hackers e pessoas que fazem mau uso do conhecimento matemático possam causar danos a sociedade, seja por uma simples mensagem ou até mesmo através de situações mais imprudentes como as transações bancárias indevidas / This research was conducted with the intention of motivating the study of cryptography, showing that mathematics and the communication are present at various times, both past and present. This work shows the origin of cryptanalysis and all its evolution giving emphasis on coding and decoding mechanisms through practical examples. In addition, some methods cryptographic are highlighted as the monoalphabetic substitution cipher, the Vigenere cipher, RSA encryption that is the best known method of public key cryptography , ciphers Hill, the method of linear transformations and the Rabin method, due to its great importance for the evolution of computer systems and signatures digital among others. Finally, we show the importance and the need for cryptographic resources these days, in an attempt to prevent hackers and people who make bad use of mathematical knowledge can cause damage to society, whether by a simple message or through more situations reckless as improper banking transactions

Esta pesquisa foi realizada com a intenção de motivar o estudo da criptografia, mostrando que a matemática e a comunicação estão presentes em diversos momentos, tanto no passado quanto no presente. Este trabalho mostra a origem da criptoanálise e toda a sua evolução dando ênfase nos mecanismos de codificação e decodificação através de exemplos práticos. Além disso, alguns métodos criptográficos são destacados como a cifra de substituição monoalfabética, a cifra de Vigenère, a criptografia RSA que é o método mais conhecido de criptografia de chave pública, as cifras de Hill, o método das transformações lineares e o método de Rabin, devido a sua grande importância para a evolução de sistemas computacionais e assinaturas digitais entre outros. Por fim, mostra-se a importância e a necessidade dos recursos criptográficos nos dias de hoje, na tentativa de impedir que hackers e pessoas que fazem mau uso do conhecimento matemático possam causar danos a sociedade, seja por uma simples mensagem ou até mesmo através de situações mais imprudentes como as transações bancárias indevidas / This research was conducted with the intention of motivating the study of cryptography, showing that mathematics and the communication are present at various times, both past and present. This work shows the origin of cryptanalysis and all its evolution giving emphasis on coding and decoding mechanisms through practical examples. In addition, some methods cryptographic are highlighted as the monoalphabetic substitution cipher, the Vigenere cipher, RSA encryption that is the best known method of public key cryptography , ciphers Hill, the method of linear transformations and the Rabin method, due to its great importance for the evolution of computer systems and signatures digital among others. Finally, we show the importance and the need for cryptographic resources these days, in an attempt to prevent hackers and people who make bad use of mathematical knowledge can cause damage to society, whether by a simple message or through more situations reckless as improper banking transactions

From the time of the Greeks, primality testing and factoring have fascinated mathematicians, and for centuries following the Greeks primality testing and factorization were pursued by enthusiasts and professional mathematicians for their intrisic value. There was little practical application. One example application was to determine whether or not the Fermat numbers, that is, numbers of the form F;, = 2'" + 1 were prime. Fermat conjectured that for all n they were prime. For n = 1,2,3,4, the Fermat numbers are prime, but Euler showed that F; was not prime and to date no F,, n 2 5 has been found to be prime. Thus, for nearly 2000 years primality testing and factorization was largely pure mathematics. This all changed in the mid 1970's with the advent of public key cryptography. Large prime numbers are used in generating keys in many public key cryptosystems and the security of many of these cryptosystems depends on the difficulty of factoring numbers with large prime factors. Thus, the race was on to develop new algorithms to determine the primality or otherwise of a given large integer and to determine the factors of given large integers. The development of such algorithms continues today. This thesis develops both of these themes. The first part of this thesis deals with primality testing and after a brief introduction to primality testing a new probabilistic primality algorithm, ALI, is introduced. It is analysed in detail and compared to Fermat and Miller-Rabin primality tests. It is shown that the ALI algorithm is more efficient than the Miller-Rabin algorithm in some aspects. The second part of the thesis deals with factoring and after looking closely at various types of algorithms a new algorithm, RAK, is presented. It is analysed in detail and compared with Fermat factorization. The RAK algorithm is shown to be significantly more efficient than the Fermat factoring algorithm. A number of enhancements is made to the basic RAK algorithm in order to improve its performance. The RAK algorithm with its enhancements is known as IMPROVEDRAK. In conjunction with this work on factorization an improvement to Shor's factoring algorithm is presented. For many integers Shor's algorithm uses a quantum computer multiple times to factor a composite number into its prime factors. It is shown that Shor's alorithm can be modified in a way such that the use of a quantum computer is required just once. The common thread throughout this thesis is the application of factoring and primality testing techniques to integer types which commonly occur in public key cryptosystems. Thus, this thesis contributes not only in the area of pure mathematics but also in the very contemporary area of cryptology.

Submitted by LUCIANA SAAB null (lcn.saab@gmail.com) on 2016-09-21T20:31:08Z No. of bitstreams: 1 DISSERTAÇÃO ANVERSO LUCIANA SAAB.pdf: 1483729 bytes, checksum: a711e48980c086f15ceb25c3334a7e5c (MD5) / Rejected by Juliano Benedito Ferreira (julianoferreira@reitoria.unesp.br), reason: Solicitamos que realize uma nova submissão seguindo a orientação abaixo: O arquivo submetido não contém o certificado de aprovação. Corrija esta informação e realize uma nova submissão contendo o arquivo correto. Agradecemos a compreensão. on 2016-09-27T12:33:50Z (GMT) / Submitted by LUCIANA SAAB null (lcn.saab@gmail.com) on 2016-09-30T17:44:03Z No. of bitstreams: 1 DISSERTAÇÃO ANVERSO LUCIANA SAAB.pdf: 1484031 bytes, checksum: cd04f99fa27da37b352ad2b4437d3f25 (MD5) / Approved for entry into archive by Ana Paula Grisoto (grisotoana@reitoria.unesp.br) on 2016-09-30T19:46:39Z (GMT) No. of bitstreams: 1 saab_l_me_mar.pdf: 1484031 bytes, checksum: cd04f99fa27da37b352ad2b4437d3f25 (MD5) / Made available in DSpace on 2016-09-30T19:46:39Z (GMT). No. of bitstreams: 1 saab_l_me_mar.pdf: 1484031 bytes, checksum: cd04f99fa27da37b352ad2b4437d3f25 (MD5) Previous issue date: 2016-08-26 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Este trabalho retoma a assinatura dos Acordos de Oslo entre israelenses e palestinos em setembro de 1993 a partir do entendimento de que os termos necessários para a resolução do conflito histórico não são discutidos no processo de paz. No decorrer da análise do texto do primeiro documento a ser assinado, a Declaração de Princípios (DOP), percebe-se que o conteúdo da proposta de paz e a fórmula de negociações bilaterais adotada não propõem uma alteração da assimetria de poder existente entre palestinos da OLP e o Estado de Israel, o que torna o processo desigual e extremamente favorável à continuação da ocupação militar israelense sobre os territórios da Faixa de Gaza e da Cisjordânia. O trabalho, portanto, foca sua análise no processo de negociação anterior à assinatura da DOP e no contexto político e econômico dos responsáveis por Oslo para estabelecer quais foram os interesses envolvidos em fechar um acordo e de que maneira eles influenciaram a redação dos termos da declaração. Durante a pesquisa, notamos que os Acordos de Oslo beneficiaram exclusivamente os atores envolvidos nas negociações secretas na Noruega, a OLP e israelenses do partido trabalhista, o que nos permite afirmar que o processo de paz não foi representativo dos diversos setores políticos palestinos e israelenses. O estudo também revela que a proposta de paz oferecida aos palestinos em Oslo é uma formulação israelense que remete ao início do processo de paz no Oriente Médio no ano de 1978, cujo principal objetivo foi a normalização das relações diplomáticas entre israelenses e os Estados árabes vizinhos. Assim, as condições negociadas na ocasião de Oslo partiram de um antigo pressuposto de que a paz regional não pressupõe a criação do Estado palestino, mas apenas o direito de autorrepresentação dos residentes dos territórios ocupados. Essas condições foram aceitas pela liderança de Yasser Arafat como estratégia para obter prestígio político e retornar ao território da Palestina. Concluímos, portanto, que o processo de paz de Oslo não se tratou de uma legítima iniciativa para estabelecer a paz de maneira justa e igualitária na região, conforme divulgado por Israel e pelos Estados Unidos, mas de um acordo entre o partido trabalhista e os palestinos da OLP, elaborado de uma maneira que possibilitou a expansão territorial israelense sobre Gaza e Cisjordânia, desconsiderou a questão dos refugiados e não reconheceu o direito à autodeterminação nacional palestina. / This paper refers to the signing of the Oslo Accords between Israel and the Palestinians in September 1993 from the understanding that the necessary terms in order to solve the historical conflict are not discussed in the peace process. The reading of the first document to be signed, the Declaration of Principles (DOP), reveals that the contents of the peace proposal and the bilateral negotiations formula do not alter the existing asymmetry of power between Palestinians from the PLO and the State of Israel, which makes the uneven process extremely favorable to the continuation of the Israeli military occupation over the territories of Gaza and the West Bank. The paper therefore focuses its analysis on the negotiation process previous to the signing of the DOP and the political and economic context of those responsible for Oslo, in order to establish what were the interests involved and how they influenced the drafting of the terms of the Declaration. During the research, it becomes clear that the Oslo agreements only benefited the actors involved in secret negotiations in Norway, namely the PLO and Israeli Labor Party, which allows us to state that the peace process was not representative of the various Palestinian and Israeli political sectors. The study also reveals that the peace proposal made to the Palestinians in Oslo is an Israeli formulation, that refers back to the beginning of the peace process in the Middle East in 1978, whose main goal was the normalization of diplomatic relations between Israel and the Arab neighboring states . Thus, the conditions discussed in Oslo were based on an old assumption that regional peace does not imply in the creation of a Palestinian state, but only the right to self-representation of the Palestinian residents in the occupied territories. These conditions were accepted by Yasser Arafat as a strategy to gain political prestige and return to the territory of Palestine. We conclude therefore that the Oslo peace process was not a legitimate initiative to establish a fair and equal peace in the region, as claimed by Israel and the United States, but an agreement made between the Israeli Labour Party and the PLO, drafted to enabled the Israeli territorial expansion over the West Bank and Gaza, to dismiss the question of refugees and not recognize the Palestinian’s right to national self-determination.

Denna uppsats hanterar hur kvinnliga karaktärer porträtteras i romantisk komedi genom att närmare studera begreppet ”Manic Pixie Dream Girl”. Detta begrepp leder till missförstånd om kvinnans roll i filmens värld och skapar diskussioner om jämställdhet och västerländsk berättarkultur. Syftet med denna uppsats är att undersöka två kvinnor i två olika romantiska komedier uppfyller de kriterier som nämns av Manic Pixie Dream Girl-begreppets myntare, Nathan Rabin, har lagt fram och om det således är motiverat att argumentera att karaktärerna upprätthåller sexistiska synsätt. Den teoretiska grund som uppsatsen bygger på kommer främst från feministisk teori, men även från Laura Mulveys teori om skopofili och den manliga blicken. För att analysera det utvalda materialet används en skräddarsydd karaktärsanalytisk metod. Resultatet visar att, trots att de kvinnliga karaktärerna må uppfylla några eller flera av de kriterier som Rabin ställer fram så innebär inte det direkt att karaktärerna är endimensionella och, i förlängning, overkliga porträtt av kvinnor i allmänhet. / This essay deals with how female characters are portrayed in romantic comedies by studying the "Manic Pixie Dream Girl"-phenomenon closer. This concept leads to misunderstandings about women's roles in the world of cinema and creates discussions about equality and Western storytelling. The purpose of this essay is to study two women in two different romantic comedies and study if they meet the criteria Nathan Rabin, the man who coined the term “Manic Pixie Dream Girl”, has announced to be qualities of a Manic Pixie Dream Girl and whether it is justified to argue that the female characters maintain sexist ideals. The theoretical basis on which the essay is based primarily comes from feminist theory, but also from Laura Mulvey’s theory of scopophilia and “the male gaze”. To analyze the selected material I have chosen to use a customized method of character analysis. The results show that, despite the fact that the female characters may meet some or more of the criteria Rabin have announced, the material does not directly imply that the characters are one-dimensional and, in extension, improbable and unreal portraits of women in general.