Testiranje i dokazivanje prostosti i primjene rezultata u kriptografiji

undergraduate thesis

• Title (english): Primality testing and proving and results appliance in cryptography
• Author: Alen Kokotec-Lovrek
• Mentor: Marcel Maretić (mentor); MBZ: 253492
• Committee member: Damir Horvat (predsjednik povjerenstva); MBZ: 264435
• Granter: University of Zagreb; Faculty of Organization and Informatics; (Department of Quantitative Methods); Varaždin
• Defense date and country: 2018-09-12, Croatia
• Scientific / art field, discipline and subdiscipline: SOCIAL SCIENCES; Information and Communication Sciences; Organization and Informatics

Abstract

Tema ovog rada je testiranje prostosti. Dovoljna je pseudoprostost, tj. da znamo da je broj vrlo vjerojatno prost. Faktorizacija većih brojeva na proste faktore nije jednostavna. Objašnjeni su pojmovi prostih brojeva, same pseudoprostosti u bazi i jake pseudoprostosti u bazi, kongruencije, Eulerove funkcije, modularnog potenciranja. Obrađeni su Legendreov i Jacobijev simbol za potrebe testova prostosti. Središnji dio rada su probabilistički testovi prostosti kojima se ispituje prostost broja zadovoljavajućom točnošću. Radi se o Fermatovom testu, Solovay-Strassenovom testu i Miller-Rabinovom testu. Testovi su objašnjeni i algoritamski, također su potkrijepljeni primjerima izračuna. Naposlijetku, veliki pseudoprosti ili prosti brojevi nalaze primjenu u kriptografiji kako bi se poruke prenosile na što sigurniji način.

• Keywords: kriptografija; diskretna matematika; teorija brojeva; prosti brojevi
• Language: croatian
• URN:NBN: urn:nbn:hr:211:638658
• Study programme: Title: Information Systems; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/prvostupnica (baccalaureus/baccalaurea) informatike (sveučilišni/a prvostupnik/prvostupnica (baccalaureus/baccalaurea) informatike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2019-03-04 11:42:00