аЯрЁБс>ўџ /1ўџџџ.џџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџьЅСq`№П˜bjbjqPqP7"::˜џџџџџџЄ№№№№№№№       8&, , , , , , , , ЗЙЙЙЙЙЙ$^hЦЊн№e, , eeн№№, , ђccce№, №, ЗceЗcc№№c, P•ѕgŠе sІc›08cp4pcp№c8,  Ь rc> \š Ы, , , ннM, , , 8eeee           №№№№№№џџџџ Tэtulo: Uma Versуo Quтntica do Algoritmo Rє de Pollard Resumo: O algoritmo de Shor estс entre os mais impressionantes da computaчуo quтntica, mas o estado da arte em fatoraчуo nуo se lhe resume. O tema щ muito mais rico. Ocorre neste momento uma evoluчуo do estado da arte em fatoraчуo. Hс novos algoritmos que se desempenham melhor que o algoritmo de Shor para certas classes de compostos bem como melhor que todos os algoritmos clсssicos. Щ certo que algoritmos clсssicos nуo sуo completamente substituэveis pelo algoritmo de Shor, a depender do tamanho do composto a ser fatorado. Щ menos ѓbvio, entretanto, que existam algoritmos quтnticos de fatoraчуo que sejam, para muitos compostos, mais rсpidos que o algoritmo de Shor e mais rсpidos que todos os algoritmos clсssicos conhecidos. No modelo clсssico de computaчуo, o estado da arte em fatoraчуo щ uma composiчуo de quatro algoritmos, que, devido a seus desempenhos, devem ser executados em uma ordem especэfica na busca por um fator nуo-trivial do natural composto que se deseja fatorar. Sуo eles o mщtodo da divisуo tentativa, o algoritmo Rє de Pollard, o algoritmo de curvas elэpticas e o quarto podendo ser o quadratic sieve ou o general number field sieve. O mщtodo de curvas elэpticas e o general number field sieve foram traduzidos para o modelo quтntico, superando o algoritmo de Shor em alguns casos, mostrando que traduzir estratщgias clсssicas para suas versѕes quтnticas щ uma abordagem interessante. Apresentamos uma versуo quтntica da divisуo tentativa e do algoritmo Rє de Pollard. A divisуo tentativa, no modelo quтntico de computaчуo, supera o modelo clсssico em um fator quadrсtico, pertencendo р classe de complexidade O(N^1/4), sendo N o natural composto que se deseja fatorar. Jс o algoritmo Rє de Pollard, no modelo quтntico, depende de soluчуo de um problema em aberto, que apresentamos, para que supere a complexidade do modelo clсssico. A soluчуo alternativa que encontramos para traduzir o algoritmo para o modelo quтntico equipara-se р complexidade no modelo clсssico, O(N^1/4). Tambщm apresentamos uma anсlise do algoritmo de Euclides para computar o maior divisor comum, do algoritmo de Floyd para detecчуo de ciclos, do algoritmo Rє de Pollard para fatoraчуo e do algoritmo de Grover para busca. Palavras-chave: fatoraчуo; Algoritmo Rє de Pollard; Algoritmo de Floyd para detecчуo de ciclos; Algoritmo de Grover; Algoritmos Quтnticos. Abstract: Shor’s algorithm is one of the most impressive results of quantum computing, but it is not the whole of the state-of-the-art. Factoring is a much richer subject. There is an evolution of the state-of-the-art in factoring taking place at this very moment. New algorithms are outperforming Shor’s algorithm in some cases and also outperforming all classical algorithms. It’s certain that classical algorithms aren’t completely replaceable by Shor’s algorithm, depending on the size of the composite one wishes to factor. It’s less obvious, however, that there are quantum factoring algorithms which are, for many composites, faster than Shor’s and faster than all known pre-quantum algorithms. In the classical model of computation, the state-of-the-art in factoring is a composition of four algorithms. Due to their performances, they are executed in a specific order in the search for a non-trivial factor of the composite number one wishes to factor. They are the trial division method, Pollard’s Rho algorithm, the elliptic curve method and the fourth algorithm being the quadratic sieve or the general number field sieve. The elliptic curve method and the general number field sieve were translated to the quantum model, outperforming Shor’s algorithm in some cases, showing that translating classical strategies to their quantum versions is an interesting approach. We present a quantum version of trial division and of Pollard’s Rho. Trial division, in the quantum model of computation, outperforms the classical model version by a quadratic factor and belongs to the complexity class O(N^1/4), where N is the natural composite one wishes to factor. The quantum version of Pollard’s Rho, however, depends on a solution of an open problem, which we present, so that it can outperform the complexity of the classical model. The alternative solution we found to translate the algorithm to the quantum model yields the same complexity class as that of the classical model, O(N^1/4). We also present an analysis of Euclid’s algorithm for computing the greatest common divisor, Floyd’s algorithm for cycle detection, Pollard’s Rho for factorization and Grover’s algorithm for searching. Keywords: factoring. Pollard's Rho Algorithm. Floyd's Algorithm for cycle detection. Grover's Algorithm. Quantum Algorithms. 7>A” Ѓ Љ У ц  юќ !LMabyz„Œ#˜ђчђпчбчбчбчХКЏКЏКЏКЏКчЈЁ™Ё™hк иhЄtm hк и5\ hЄtm5\hЄtmhзH3mHsHhЄtmhк иmHsHhЄtmhк и5mHsHhзH3hк и6]mHsHhЄtmmHsHhзH3hк иmHsHhзH3hк и5\mHsH78@AэюCyz{|}~€‚ƒ„Ž˜§§§§ѕ§ѕѕ§§§§§§§§§§§§§ѕ§§$a$gdЄtm˜§50P:pUhяАа/ Ар=!А "А #‰$‰%ААаАа а†œ 666666666666666666666666666666666666666666 6666666666 666666666666 666666666666666666666666666666666666666666666666666666666666666666F@ёџF NormaldCJ_HaJmH sH tHF@QRF Uhя0Tэtulo 1$$ЄЄx@&CJ(aJ(F@QRF Uhя0Tэtulo 2$$ЄhЄx@&CJ aJ P@QRP Uhя0Tэtulo 3$$Є@ЄP@&B*CJaJphCCCP@QRP Uhя0Tэtulo 4$$ЄЄP@&B*CJaJphfffH@QRH Uhя0Tэtulo 5$$Є№ЄP@& B*phfffN@QRN Uhя0Tэtulo 6$$Є№ЄP@&6B*]phfff>A@ђџЁ> 0Fonte parсg. padrуoTiѓџГT 0 Tabela normalі4ж l4жaі ,kєџС, 0 Sem lista XўOЂёX щoЭ Char Char7*5CJ KH OJPJQJ\^JaJ mH sH ZўЂZ щoЭ Char Char6,56CJOJPJQJ\]^JaJmH sH TўЂT щoЭ Char Char5&5CJOJPJQJ\^JaJmH sH TўЂ!T щoЭ Char Char4&5CJOJPJQJ\^JaJmH sH ZўЂ1Z щoЭ Char Char3,56CJOJPJQJ\]^JaJmH sH LўЂAL щoЭ Char Char25OJPJQJ\^JmH sH FўOёџRF Uhя0normaldCJ_HaJmH sH tH:>@QR: Uhя0Tэtulo $$Є<CJ4aJ4XўOЂqX щoЭ  Char Char1*5CJ KHOJPJQJ\^JaJ mH sH JJ@QRJ Uhя0 Subtэtulo $$Є@B*CJaJphfffLўOЂ‘L щoЭА Char Char CJOJPJQJ^JaJmH sH ˜"џџџџ78@AэюC y z { | } ~  €  ‚ ƒ „ Ž  š˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜˜˜џџ —C z9˜CЬy9™C y9šCŒy9›CŒz9œCЬz9C {9žCL{9ŸC\OЏ CœOЏЁCмOЏu u ))''nнн::š  x x ,,**tрр==š 9 *€urn:schemas-microsoft-com:office:smarttags€place€8 *€urn:schemas-microsoft-com:office:smarttags€City€  вL )+/6PTbf@HейLNRY”žЃБЗИНОУюєѕњћCG дльюђљ„Ћ­БИкр   / 4 [ a „ Œ  • Џ Е G M  u x ek),'*нр:=š<GЁЃ : B C E „  „ Š ХЧEG0HIopƒ„—š33333338@„   p—š„ Œ šхзH3YBF$7aЄtm21†pWИк иUhя„ šџ@€„ „ ”Zд„ „ ˜@@џџUnknownџџџџџџџџџџџџGџ:рAxР џTimes New Roman5€Symbol3& џ:рCxР џArial7џрџ@ŸCambria7&џрџЌ@ŸCalibri"Aˆ№аЉNыt'fТz‡чБ !чБ !!№ ‰ДД24№ќџ(№џ$PџџџџџџџџџџџџџџџџџџџџџUhя2џџ6Tэtulo: Uma Versуo Quтntica do Algoritmo Rє de PollardHelioHelioўџр…ŸђљOhЋ‘+'Гй0œ˜ифє  ,8 X d p|„Œ”ф8Tэtulo: Uma Versуo Quтntica do Algoritmo Rє de PollardHelioNormalHelio5Microsoft Office Word@Ј[щ@ёІўд@„ЕоgŠечБўџеЭеœ.“—+,љЎ0  hp|„Œ” œЄЌД М џф! ц 7Tэtulo: Uma Versуo Quтntica do Algoritmo Rє de Pollard Tэtulo ўџџџўџџџ !"#$%ўџџџ'()*+,-ўџџџ§џџџ0ўџџџўџџџўџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџRoot Entryџџџџџџџџ РFа>#ѕgŠе2€1TableџџџџџџџџpWordDocumentџџџџџџџџ7"SummaryInformation(џџџџDocumentSummaryInformation8џџџџџџџџџџџџ&CompObjџџџџџџџџџџџџuџџџџџџџџџџџџџџџџџџџџџџџџўџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџўџ џџџџ РF#Documento do Microsoft Office Word MSWordDocWord.Document.8є9Вq