CINXE.COM

<!doctype html> <html lang="hu" class="no-js" lang="en"> <head> <meta charset="utf-8" /> <meta http-equiv="x-ua-compatible" content="ie=edge"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <link rel="pingback" href="https://youproof.hu/xmlrpc.php"> <meta name='robots' content='index, follow, max-image-preview:large, max-snippet:-1, max-video-preview:-1' />  <title>Prímteszt, Fermat-prímteszt, Miller-Rabin-prímteszt - YOUPROOF</title> <meta name="description" content="Prímszámok keresése. Fermat-prímteszt. Carmichael számok és univerzális álprímek. Miller-Rabin-prímteszt. Fermat és Miller-Rabin-tanúk. Fermat-faktorizáció." /> <link rel="canonical" href="https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/" /> <meta property="og:locale" content="hu_HU" /> <meta property="og:type" content="article" /> <meta property="og:title" content="Alice és Bob - Kriptográfia, rejtjelezés" /> <meta property="og:description" content="23. rész: Alice és Bob prímszámok után nyomoz" /> <meta property="og:url" content="https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/" /> <meta property="og:site_name" content="YOUPROOF" /> <meta property="article:published_time" content="2020-06-09T07:04:38+00:00" /> <meta property="article:modified_time" content="2020-12-18T13:17:22+00:00" /> <meta property="og:image" content="https://youproof.hu/wp-content/uploads/kriptografia_23_thumbnail_facebook-1.jpg" /> <meta property="og:image:width" content="1200" /> <meta property="og:image:height" content="630" /> <meta property="og:image:type" content="image/jpeg" /> <meta name="author" content="Moldvai Dávid" /> <meta name="twitter:card" content="summary_large_image" /> <meta name="twitter:label1" content="Szerző:" /> <meta name="twitter:data1" content="Moldvai Dávid" /> <meta name="twitter:label2" content="Becsült olvasási idő" /> <meta name="twitter:data2" content="51 perc" /> <script type="application/ld+json" class="yoast-schema-graph">{"@context":"https://schema.org","@graph":[{"@type":"Article","@id":"https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/#article","isPartOf":{"@id":"https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/"},"author":{"name":"Moldvai Dávid","@id":"https://youproof.hu/#/schema/person/529c774d4e6617f648fb33734de2dec4"},"headline":"Alice és Bob prímszámok után nyomoz","datePublished":"2020-06-09T07:04:38+00:00","dateModified":"2020-12-18T13:17:22+00:00","mainEntityOfPage":{"@id":"https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/"},"wordCount":10282,"commentCount":0,"publisher":{"@id":"https://youproof.hu/#/schema/person/529c774d4e6617f648fb33734de2dec4"},"image":{"@id":"https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/#primaryimage"},"thumbnailUrl":"https://youproof.hu/wp-content/uploads/kriptografia_23_thumbnail_orig-1.jpg","keywords":["asszociált","Bézout-lemma","Carmichael-szám","egység","euklidészi algoritmus","felbonthatatlan","Fermat-faktorizáció","Fermat-prímteszt","kínai maradéktétel","kis Fermat-tétel","kongruencia","kongruenciarendszer","maradékosztály","Miller-Rabin-prímteszt","prím","prímteszt","relatív prím","univerzális álprím"],"articleSection":["Elemi számelmélet"],"inLanguage":"hu","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/#respond"]}]},{"@type":"WebPage","@id":"https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/","url":"https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/","name":"Prímteszt, Fermat-prímteszt, Miller-Rabin-prímteszt - YOUPROOF","isPartOf":{"@id":"https://youproof.hu/#website"},"primaryImageOfPage":{"@id":"https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/#primaryimage"},"image":{"@id":"https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/#primaryimage"},"thumbnailUrl":"https://youproof.hu/wp-content/uploads/kriptografia_23_thumbnail_orig-1.jpg","datePublished":"2020-06-09T07:04:38+00:00","dateModified":"2020-12-18T13:17:22+00:00","description":"Prímszámok keresése. Fermat-prímteszt. Carmichael számok és univerzális álprímek. Miller-Rabin-prímteszt. Fermat és Miller-Rabin-tanúk. Fermat-faktorizáció.","breadcrumb":{"@id":"https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/#breadcrumb"},"inLanguage":"hu","potentialAction":[{"@type":"ReadAction","target":["https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/"]}]},{"@type":"ImageObject","inLanguage":"hu","@id":"https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/#primaryimage","url":"https://youproof.hu/wp-content/uploads/kriptografia_23_thumbnail_orig-1.jpg","contentUrl":"https://youproof.hu/wp-content/uploads/kriptografia_23_thumbnail_orig-1.jpg","width":1200,"height":630},{"@type":"BreadcrumbList","@id":"https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https://youproof.hu/"},{"@type":"ListItem","position":2,"name":"Alice és Bob prímszámok után nyomoz"}]},{"@type":"WebSite","@id":"https://youproof.hu/#website","url":"https://youproof.hu/","name":"YOUPROOF","description":"","publisher":{"@id":"https://youproof.hu/#/schema/person/529c774d4e6617f648fb33734de2dec4"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https://youproof.hu/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"hu"},{"@type":["Person","Organization"],"@id":"https://youproof.hu/#/schema/person/529c774d4e6617f648fb33734de2dec4","name":"Moldvai Dávid","image":{"@type":"ImageObject","inLanguage":"hu","@id":"https://youproof.hu/#/schema/person/image/","url":"https://youproof.hu/wp-content/uploads/2019/04/cropped-logo_full_big-1.png","contentUrl":"https://youproof.hu/wp-content/uploads/2019/04/cropped-logo_full_big-1.png","width":467,"height":155,"caption":"Moldvai Dávid"},"logo":{"@id":"https://youproof.hu/#/schema/person/image/"}}]}</script>  <link rel='dns-prefetch' href='//fonts.googleapis.com' /> <link rel="alternate" type="application/rss+xml" title="YOUPROOF » hírcsatorna" href="https://youproof.hu/feed/" /> <link rel="alternate" type="application/rss+xml" title="YOUPROOF » hozzászólás hírcsatorna" href="https://youproof.hu/comments/feed/" /> <link rel="alternate" type="application/rss+xml" title="YOUPROOF » Alice és Bob prímszámok után nyomoz hozzászólás hírcsatorna" href="https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/feed/" /> <script type="text/javascript"> /* <![CDATA[ */ window._wpemojiSettings = {"baseUrl":"https:\/\/s.w.org\/images\/core\/emoji\/15.0.3\/72x72\/","ext":".png","svgUrl":"https:\/\/s.w.org\/images\/core\/emoji\/15.0.3\/svg\/","svgExt":".svg","source":{"concatemoji":"https:\/\/youproof.hu\/wp-includes\/js\/wp-emoji-release.min.js?ver=6.5.5"}}; /*! This file is auto-generated */ !function(i,n){var o,s,e;function c(e){try{var t={supportTests:e,timestamp:(new Date).valueOf()};sessionStorage.setItem(o,JSON.stringify(t))}catch(e){}}function p(e,t,n){e.clearRect(0,0,e.canvas.width,e.canvas.height),e.fillText(t,0,0);var t=new Uint32Array(e.getImageData(0,0,e.canvas.width,e.canvas.height).data),r=(e.clearRect(0,0,e.canvas.width,e.canvas.height),e.fillText(n,0,0),new Uint32Array(e.getImageData(0,0,e.canvas.width,e.canvas.height).data));return t.every(function(e,t){return e===r[t]})}function u(e,t,n){switch(t){case"flag":return n(e,"\ud83c\udff3\ufe0f\u200d\u26a7\ufe0f","\ud83c\udff3\ufe0f\u200b\u26a7\ufe0f")?!1:!n(e,"\ud83c\uddfa\ud83c\uddf3","\ud83c\uddfa\u200b\ud83c\uddf3")&&!n(e,"\ud83c\udff4\udb40\udc67\udb40\udc62\udb40\udc65\udb40\udc6e\udb40\udc67\udb40\udc7f","\ud83c\udff4\u200b\udb40\udc67\u200b\udb40\udc62\u200b\udb40\udc65\u200b\udb40\udc6e\u200b\udb40\udc67\u200b\udb40\udc7f");case"emoji":return!n(e,"\ud83d\udc26\u200d\u2b1b","\ud83d\udc26\u200b\u2b1b")}return!1}function f(e,t,n){var r="undefined"!=typeof WorkerGlobalScope&&self instanceof WorkerGlobalScope?new OffscreenCanvas(300,150):i.createElement("canvas"),a=r.getContext("2d",{willReadFrequently:!0}),o=(a.textBaseline="top",a.font="600 32px Arial",{});return e.forEach(function(e){o[e]=t(a,e,n)}),o}function t(e){var t=i.createElement("script");t.src=e,t.defer=!0,i.head.appendChild(t)}"undefined"!=typeof Promise&&(o="wpEmojiSettingsSupports",s=["flag","emoji"],n.supports={everything:!0,everythingExceptFlag:!0},e=new Promise(function(e){i.addEventListener("DOMContentLoaded",e,{once:!0})}),new Promise(function(t){var n=function(){try{var e=JSON.parse(sessionStorage.getItem(o));if("object"==typeof e&&"number"==typeof e.timestamp&&(new Date).valueOf()<e.timestamp+604800&&"object"==typeof e.supportTests)return e.supportTests}catch(e){}return null}();if(!n){if("undefined"!=typeof Worker&&"undefined"!=typeof OffscreenCanvas&&"undefined"!=typeof URL&&URL.createObjectURL&&"undefined"!=typeof Blob)try{var e="postMessage("+f.toString()+"("+[JSON.stringify(s),u.toString(),p.toString()].join(",")+"));",r=new Blob([e],{type:"text/javascript"}),a=new Worker(URL.createObjectURL(r),{name:"wpTestEmojiSupports"});return void(a.onmessage=function(e){c(n=e.data),a.terminate(),t(n)})}catch(e){}c(n=f(s,u,p))}t(n)}).then(function(e){for(var t in e)n.supports[t]=e[t],n.supports.everything=n.supports.everything&&n.supports[t],"flag"!==t&&(n.supports.everythingExceptFlag=n.supports.everythingExceptFlag&&n.supports[t]);n.supports.everythingExceptFlag=n.supports.everythingExceptFlag&&!n.supports.flag,n.DOMReady=!1,n.readyCallback=function(){n.DOMReady=!0}}).then(function(){return e}).then(function(){var e;n.supports.everything||(n.readyCallback(),(e=n.source||{}).concatemoji?t(e.concatemoji):e.wpemoji&&e.twemoji&&(t(e.twemoji),t(e.wpemoji)))}))}((window,document),window._wpemojiSettings); /* ]]> */ </script> <style id='wp-emoji-styles-inline-css' type='text/css'> img.wp-smiley, img.emoji { display: inline !important; border: none !important; box-shadow: none !important; height: 1em !important; width: 1em !important; margin: 0 0.07em !important; vertical-align: -0.1em !important; background: none !important; padding: 0 !important; } </style> <link rel='stylesheet' id='wp-block-library-css' href='https://youproof.hu/wp-includes/css/dist/block-library/style.min.css?ver=6.5.5' type='text/css' media='all' /> <style id='classic-theme-styles-inline-css' type='text/css'> /*! This file is auto-generated */ .wp-block-button__link{color:#fff;background-color:#32373c;border-radius:9999px;box-shadow:none;text-decoration:none;padding:calc(.667em + 2px) calc(1.333em + 2px);font-size:1.125em}.wp-block-file__button{background:#32373c;color:#fff;text-decoration:none} </style> <style id='global-styles-inline-css' type='text/css'> body{--wp--preset--color--black: #000000;--wp--preset--color--cyan-bluish-gray: #abb8c3;--wp--preset--color--white: #ffffff;--wp--preset--color--pale-pink: #f78da7;--wp--preset--color--vivid-red: #cf2e2e;--wp--preset--color--luminous-vivid-orange: #ff6900;--wp--preset--color--luminous-vivid-amber: #fcb900;--wp--preset--color--light-green-cyan: #7bdcb5;--wp--preset--color--vivid-green-cyan: #00d084;--wp--preset--color--pale-cyan-blue: #8ed1fc;--wp--preset--color--vivid-cyan-blue: #0693e3;--wp--preset--color--vivid-purple: #9b51e0;--wp--preset--gradient--vivid-cyan-blue-to-vivid-purple: linear-gradient(135deg,rgba(6,147,227,1) 0%,rgb(155,81,224) 100%);--wp--preset--gradient--light-green-cyan-to-vivid-green-cyan: linear-gradient(135deg,rgb(122,220,180) 0%,rgb(0,208,130) 100%);--wp--preset--gradient--luminous-vivid-amber-to-luminous-vivid-orange: linear-gradient(135deg,rgba(252,185,0,1) 0%,rgba(255,105,0,1) 100%);--wp--preset--gradient--luminous-vivid-orange-to-vivid-red: linear-gradient(135deg,rgba(255,105,0,1) 0%,rgb(207,46,46) 100%);--wp--preset--gradient--very-light-gray-to-cyan-bluish-gray: linear-gradient(135deg,rgb(238,238,238) 0%,rgb(169,184,195) 100%);--wp--preset--gradient--cool-to-warm-spectrum: linear-gradient(135deg,rgb(74,234,220) 0%,rgb(151,120,209) 20%,rgb(207,42,186) 40%,rgb(238,44,130) 60%,rgb(251,105,98) 80%,rgb(254,248,76) 100%);--wp--preset--gradient--blush-light-purple: linear-gradient(135deg,rgb(255,206,236) 0%,rgb(152,150,240) 100%);--wp--preset--gradient--blush-bordeaux: linear-gradient(135deg,rgb(254,205,165) 0%,rgb(254,45,45) 50%,rgb(107,0,62) 100%);--wp--preset--gradient--luminous-dusk: linear-gradient(135deg,rgb(255,203,112) 0%,rgb(199,81,192) 50%,rgb(65,88,208) 100%);--wp--preset--gradient--pale-ocean: linear-gradient(135deg,rgb(255,245,203) 0%,rgb(182,227,212) 50%,rgb(51,167,181) 100%);--wp--preset--gradient--electric-grass: linear-gradient(135deg,rgb(202,248,128) 0%,rgb(113,206,126) 100%);--wp--preset--gradient--midnight: linear-gradient(135deg,rgb(2,3,129) 0%,rgb(40,116,252) 100%);--wp--preset--font-size--small: 13px;--wp--preset--font-size--medium: 20px;--wp--preset--font-size--large: 36px;--wp--preset--font-size--x-large: 42px;--wp--preset--spacing--20: 0.44rem;--wp--preset--spacing--30: 0.67rem;--wp--preset--spacing--40: 1rem;--wp--preset--spacing--50: 1.5rem;--wp--preset--spacing--60: 2.25rem;--wp--preset--spacing--70: 3.38rem;--wp--preset--spacing--80: 5.06rem;--wp--preset--shadow--natural: 6px 6px 9px rgba(0, 0, 0, 0.2);--wp--preset--shadow--deep: 12px 12px 50px rgba(0, 0, 0, 0.4);--wp--preset--shadow--sharp: 6px 6px 0px rgba(0, 0, 0, 0.2);--wp--preset--shadow--outlined: 6px 6px 0px -3px rgba(255, 255, 255, 1), 6px 6px rgba(0, 0, 0, 1);--wp--preset--shadow--crisp: 6px 6px 0px rgba(0, 0, 0, 1);}:where(.is-layout-flex){gap: 0.5em;}:where(.is-layout-grid){gap: 0.5em;}body .is-layout-flex{display: flex;}body .is-layout-flex{flex-wrap: wrap;align-items: center;}body .is-layout-flex > *{margin: 0;}body .is-layout-grid{display: grid;}body .is-layout-grid > *{margin: 0;}:where(.wp-block-columns.is-layout-flex){gap: 2em;}:where(.wp-block-columns.is-layout-grid){gap: 2em;}:where(.wp-block-post-template.is-layout-flex){gap: 1.25em;}:where(.wp-block-post-template.is-layout-grid){gap: 1.25em;}.has-black-color{color: var(--wp--preset--color--black) !important;}.has-cyan-bluish-gray-color{color: var(--wp--preset--color--cyan-bluish-gray) !important;}.has-white-color{color: var(--wp--preset--color--white) !important;}.has-pale-pink-color{color: var(--wp--preset--color--pale-pink) !important;}.has-vivid-red-color{color: var(--wp--preset--color--vivid-red) !important;}.has-luminous-vivid-orange-color{color: var(--wp--preset--color--luminous-vivid-orange) !important;}.has-luminous-vivid-amber-color{color: var(--wp--preset--color--luminous-vivid-amber) !important;}.has-light-green-cyan-color{color: var(--wp--preset--color--light-green-cyan) !important;}.has-vivid-green-cyan-color{color: var(--wp--preset--color--vivid-green-cyan) !important;}.has-pale-cyan-blue-color{color: var(--wp--preset--color--pale-cyan-blue) !important;}.has-vivid-cyan-blue-color{color: var(--wp--preset--color--vivid-cyan-blue) !important;}.has-vivid-purple-color{color: var(--wp--preset--color--vivid-purple) !important;}.has-black-background-color{background-color: var(--wp--preset--color--black) !important;}.has-cyan-bluish-gray-background-color{background-color: var(--wp--preset--color--cyan-bluish-gray) !important;}.has-white-background-color{background-color: var(--wp--preset--color--white) !important;}.has-pale-pink-background-color{background-color: var(--wp--preset--color--pale-pink) !important;}.has-vivid-red-background-color{background-color: var(--wp--preset--color--vivid-red) !important;}.has-luminous-vivid-orange-background-color{background-color: var(--wp--preset--color--luminous-vivid-orange) !important;}.has-luminous-vivid-amber-background-color{background-color: var(--wp--preset--color--luminous-vivid-amber) !important;}.has-light-green-cyan-background-color{background-color: var(--wp--preset--color--light-green-cyan) !important;}.has-vivid-green-cyan-background-color{background-color: var(--wp--preset--color--vivid-green-cyan) !important;}.has-pale-cyan-blue-background-color{background-color: var(--wp--preset--color--pale-cyan-blue) !important;}.has-vivid-cyan-blue-background-color{background-color: var(--wp--preset--color--vivid-cyan-blue) !important;}.has-vivid-purple-background-color{background-color: var(--wp--preset--color--vivid-purple) !important;}.has-black-border-color{border-color: var(--wp--preset--color--black) !important;}.has-cyan-bluish-gray-border-color{border-color: var(--wp--preset--color--cyan-bluish-gray) !important;}.has-white-border-color{border-color: var(--wp--preset--color--white) !important;}.has-pale-pink-border-color{border-color: var(--wp--preset--color--pale-pink) !important;}.has-vivid-red-border-color{border-color: var(--wp--preset--color--vivid-red) !important;}.has-luminous-vivid-orange-border-color{border-color: var(--wp--preset--color--luminous-vivid-orange) !important;}.has-luminous-vivid-amber-border-color{border-color: var(--wp--preset--color--luminous-vivid-amber) !important;}.has-light-green-cyan-border-color{border-color: var(--wp--preset--color--light-green-cyan) !important;}.has-vivid-green-cyan-border-color{border-color: var(--wp--preset--color--vivid-green-cyan) !important;}.has-pale-cyan-blue-border-color{border-color: var(--wp--preset--color--pale-cyan-blue) !important;}.has-vivid-cyan-blue-border-color{border-color: var(--wp--preset--color--vivid-cyan-blue) !important;}.has-vivid-purple-border-color{border-color: var(--wp--preset--color--vivid-purple) !important;}.has-vivid-cyan-blue-to-vivid-purple-gradient-background{background: var(--wp--preset--gradient--vivid-cyan-blue-to-vivid-purple) !important;}.has-light-green-cyan-to-vivid-green-cyan-gradient-background{background: var(--wp--preset--gradient--light-green-cyan-to-vivid-green-cyan) !important;}.has-luminous-vivid-amber-to-luminous-vivid-orange-gradient-background{background: var(--wp--preset--gradient--luminous-vivid-amber-to-luminous-vivid-orange) !important;}.has-luminous-vivid-orange-to-vivid-red-gradient-background{background: var(--wp--preset--gradient--luminous-vivid-orange-to-vivid-red) !important;}.has-very-light-gray-to-cyan-bluish-gray-gradient-background{background: var(--wp--preset--gradient--very-light-gray-to-cyan-bluish-gray) !important;}.has-cool-to-warm-spectrum-gradient-background{background: var(--wp--preset--gradient--cool-to-warm-spectrum) !important;}.has-blush-light-purple-gradient-background{background: var(--wp--preset--gradient--blush-light-purple) !important;}.has-blush-bordeaux-gradient-background{background: var(--wp--preset--gradient--blush-bordeaux) !important;}.has-luminous-dusk-gradient-background{background: var(--wp--preset--gradient--luminous-dusk) !important;}.has-pale-ocean-gradient-background{background: var(--wp--preset--gradient--pale-ocean) !important;}.has-electric-grass-gradient-background{background: var(--wp--preset--gradient--electric-grass) !important;}.has-midnight-gradient-background{background: var(--wp--preset--gradient--midnight) !important;}.has-small-font-size{font-size: var(--wp--preset--font-size--small) !important;}.has-medium-font-size{font-size: var(--wp--preset--font-size--medium) !important;}.has-large-font-size{font-size: var(--wp--preset--font-size--large) !important;}.has-x-large-font-size{font-size: var(--wp--preset--font-size--x-large) !important;} .wp-block-navigation a:where(:not(.wp-element-button)){color: inherit;} :where(.wp-block-post-template.is-layout-flex){gap: 1.25em;}:where(.wp-block-post-template.is-layout-grid){gap: 1.25em;} :where(.wp-block-columns.is-layout-flex){gap: 2em;}:where(.wp-block-columns.is-layout-grid){gap: 2em;} .wp-block-pullquote{font-size: 1.5em;line-height: 1.6;} </style> <link rel='stylesheet' id='cookie-notice-front-css' href='https://youproof.hu/wp-content/plugins/cookie-notice/css/front.min.css?ver=2.4.16' type='text/css' media='all' /> <link rel='stylesheet' id='minimumminimal-fonts-css' href='//fonts.googleapis.com/css?family=Muli%3A300%2C300i%2C600&subset=latin-ext&ver=6.5.5' type='text/css' media='all' /> <link rel='stylesheet' id='minimumminimal-mainstyle-css' href='https://youproof.hu/wp-content/themes/minimum-minimal/style.css?ver=6.5.5' type='text/css' media='all' /> <link rel='stylesheet' id='child-style-css' href='https://youproof.hu/wp-content/themes/minimum-minimal-child/style.css?ver=6.5.5' type='text/css' media='all' /> <script type="text/javascript" src="https://youproof.hu/wp-includes/js/jquery/jquery.min.js?ver=3.7.1" id="jquery-core-js"></script> <script type="text/javascript" src="https://youproof.hu/wp-includes/js/jquery/jquery-migrate.min.js?ver=3.4.1" id="jquery-migrate-js"></script> <link rel="https://api.w.org/" href="https://youproof.hu/wp-json/" /><link rel="alternate" type="application/json" href="https://youproof.hu/wp-json/wp/v2/posts/6204" /><link rel="EditURI" type="application/rsd+xml" title="RSD" href="https://youproof.hu/xmlrpc.php?rsd" /> <meta name="generator" content="WordPress 6.5.5" /> <link rel='shortlink' href='https://youproof.hu/?p=6204' /> <link rel="alternate" type="application/json+oembed" href="https://youproof.hu/wp-json/oembed/1.0/embed?url=https%3A%2F%2Fyouproof.hu%2Fkriptografia%2F23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio%2F" /> <link rel="alternate" type="text/xml+oembed" href="https://youproof.hu/wp-json/oembed/1.0/embed?url=https%3A%2F%2Fyouproof.hu%2Fkriptografia%2F23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio%2F&format=xml" /> <style type="text/css"> @font-face { font-family: 'richicons'; src: url('https://youproof.hu/wp-content/themes/minimum-minimal/font/richicons.eot?13409119'); src: url('https://youproof.hu/wp-content/themes/minimum-minimal/font/richicons.eot?13409119#iefix') format('embedded-opentype'), url('https://youproof.hu/wp-content/themes/minimum-minimal/font/richicons.woff?13409119') format('woff'), url('https://youproof.hu/wp-content/themes/minimum-minimal/font/richicons.ttf?13409119') format('truetype'), url('https://youproof.hu/wp-content/themes/minimum-minimal/font/richicons.svg?13409119#richicons') format('svg'); font-weight: normal; font-style: normal; } #top-menu, .top-bar ul ul, ul.submenu { background-color:#FFFFFF; } a #sitetitle, .top-bar a, .icon-menu, #iconmenu li:before, .top-bar ul.submenu a, .menushop .is-dropdown-submenu a, .menushop .is-dropdown-submenu a:hover{ color:#000000; } a, a:hover, .top-bar a:hover, .top-bar .current-menu-item a, .top-bar ul.submenu a:hover, #iconmenu li:hover:before, .postbox a:hover .entry-title, #copyright a:hover, #footermenu a:hover, #footer-widget-area a:hover, #top-widget-area a:hover, .pagination .prev:hover, .pagination .next:hover, .comment-metadata a:hover, .fn a:hover { color:#0066cc; } .none { background:#0066cc; } .button, .button:hover, .button:focus, .add_to_cart_button:hover, .add_to_cart_button:focus { background-color:#0066cc; color: #FFFFFF; } .entry-content a.more-link, .button, .add_to_cart_button { color:#FFFFFF; } </style> <meta name="generator" content="Elementor 3.21.1; features: e_optimized_assets_loading, additional_custom_breakpoints; settings: css_print_method-external, google_font-enabled, font_display-auto"> <link rel="icon" href="https://youproof.hu/wp-content/uploads/2019/04/cropped-logo_only_big-32x32.png" sizes="32x32" /> <link rel="icon" href="https://youproof.hu/wp-content/uploads/2019/04/cropped-logo_only_big-192x192.png" sizes="192x192" /> <link rel="apple-touch-icon" href="https://youproof.hu/wp-content/uploads/2019/04/cropped-logo_only_big-180x180.png" /> <meta name="msapplication-TileImage" content="https://youproof.hu/wp-content/uploads/2019/04/cropped-logo_only_big-270x270.png" /> <style type="text/css" id="wp-custom-css"> .typewriter { font-family: "Courier New", Courier, monospace; } .prerequisite-warning { color: red; font-style: italic; font-weight: bold; } </style>  <div id="fb-root"></div> <script async defer crossorigin="anonymous" src="https://connect.facebook.net/hu_HU/sdk.js#xfbml=1&version=v3.3"></script>  </head> <body class="post-template-default single single-post postid-6204 single-format-standard wp-custom-logo cookies-not-set elementor-default elementor-kit-4899" itemscope="itemscope" itemtype="http://schema.org/WebPage"> <header id="top-menu" class="top-bar" itemscope="itemscope"> <div class="menu-container-mobile" data-responsive-toggle="menu-container" data-hide-for="large"> <button class="icon-menu" type="button" data-toggle></button> </div> <div class="topbar-title title-logo" itemscope="itemscope" itemtype="http://schema.org/WPHeader" role="banner"> <a href="https://youproof.hu/" class="custom-logo-link" rel="home"><img fetchpriority="high" width="467" height="155" src="https://youproof.hu/wp-content/uploads/2019/04/cropped-logo_full_big-1.png" class="custom-logo" alt="YOUPROOF" decoding="async" srcset="https://youproof.hu/wp-content/uploads/2019/04/cropped-logo_full_big-1.png 467w, https://youproof.hu/wp-content/uploads/2019/04/cropped-logo_full_big-1-300x100.png 300w" sizes="(max-width: 467px) 100vw, 467px" /></a> </div> <div id="menu-container" class="menu-container"> <nav class="richprimarymenu" itemtype="http://schema.org/SiteNavigationElement" role="navigation"><ul id="menu-header-navigation-menu" class="vertical large-horizontal menu" data-responsive-menu="accordion large-dropdown"><li id="menu-item-1551" class="menu-item menu-item-type-post_type menu-item-object-page current_page_parent menu-item-1551"><a href="https://youproof.hu/blog/">Összes cikk</a></li> <li id="menu-item-1552" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-1552"><a href="https://youproof.hu/kriptografia/">Kriptográfia</a></li> </ul></nav> <ul id="iconmenu" class="menu richiconmenu"> <li id="menu-item-1073" class="menu-item menu-item-type-custom menu-item-object-custom menu-item-1073"><a href="https://www.facebook.com/youproof.hu">Facebook</a></li> <li id="searchicon" class="icon-search menu-item"> <a> Search </a> </li> </ul> </div> </header> <div id="searchwrap"> <div class= "row"> <div class="columns"> <form role="search" method="get" id="searchform" action="https://youproof.hu/"> <div class="input-group"> <input type="text" class="input-group-field" value="" name="s" id="s" placeholder="Search"> <div class="input-group-button"> <input type="submit" id="searchsubmit" value="Search" class="button"> </div> </div> </form> </div> </div> </div> <div id="herofeaturedimage" class="coverimage"> <img width="1200" height="630" src="https://youproof.hu/wp-content/uploads/kriptografia_23_thumbnail_orig-1.jpg" class="attachment-minimumminimal_single-post-cover size-minimumminimal_single-post-cover wp-post-image" alt="" decoding="async" srcset="https://youproof.hu/wp-content/uploads/kriptografia_23_thumbnail_orig-1.jpg 1200w, https://youproof.hu/wp-content/uploads/kriptografia_23_thumbnail_orig-1-768x403.jpg 768w, https://youproof.hu/wp-content/uploads/kriptografia_23_thumbnail_orig-1-1070x562.jpg 1070w" sizes="(max-width: 1200px) 100vw, 1200px" /> </div> <div id="container" class="row"> <div id="primary" class="large-7 medium-8 small-11 small-centered columns"> <article class="articlebox post-6204 post type-post status-publish format-standard has-post-thumbnail hentry category-elemi-szamelmelet tag-asszocialt tag-bezout-lemma tag-carmichael-szam tag-egyseg tag-euklideszi-algoritmus tag-felbonthatatlan tag-fermat-faktorizacio tag-fermat-primteszt tag-kinai-maradektetel tag-kis-fermat-tetel tag-kongruencia tag-kongruenciarendszer tag-maradekosztaly tag-miller-rabin-primteszt tag-prim tag-primteszt tag-relativ-prim tag-univerzalis-alprim yp_series-kriptografia"> <header class="yp-series-header"> <a href="https://youproof.hu/kriptografia/"> <div class="yp-series-logo"> <img src="https://youproof.hu/wp-content/uploads/logo_only_cryptography.png" /> </div> <div class="yp-series-title"> <h1>Episode I</h1> <h2>Alice és Bob</h2> </div> </a> </header> <header class="entry-header entry-header-single"> <h1 class="entry-title"> 23. rész: Alice és Bob prímszámok után nyomoz </h1> <div class="entry-meta">Moldvai Dávid · Posted on <time class="entry-date published" datetime="2020-06-09T09:04:38+02:00">2020.06.09.</time><time class="updated" datetime="2020-12-18T14:17:22+01:00">2020.12.18.</time></div> </header>  <div class="fb-like" data-href="https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/" data-width="100" data-layout="button" data-action="like" data-size="large" data-show-faces="false" data-share="true"></div>  <div class="entry-content"> Az <a rel="noreferrer noopener" href="https://youproof.hu/kriptografia/22-kinai-maradektetel-konguenciarendszerek-kis-fermat-tetel-rsa-bizonyitas-gyuruk-direkt-szorzata-rsa-dekodolas/" target="_blank">előző részben</a> igazoltuk, hogy az RSA rejtjelezési eljárás valóban minden esetben helyesen működik. Ezt alapvetően két fontos számelméleti összefüggés biztosította számunkra. Az első a kis Fermat-tétel (<a href="https://youproof.hu/kriptografia/22-kinai-maradektetel-konguenciarendszerek-kis-fermat-tetel-rsa-bizonyitas-gyuruk-direkt-szorzata-rsa-dekodolas/#yp-element-5892" class="yp-element-link">22.1. Tétel</a>), amely a <a rel="noreferrer noopener" href="https://youproof.hu/kriptografia/20-kongruencia-redukalt-maradekosztaly-euler-fuggveny-linearis-kongruencia-maradekrendszer-euler-fermat-tetel/" target="_blank">20. részben</a> ismertetett Euler-Fermat tétel (<a href="https://youproof.hu/kriptografia/20-kongruencia-redukalt-maradekosztaly-euler-fuggveny-linearis-kongruencia-maradekrendszer-euler-fermat-tetel/#yp-element-5507" class="yp-element-link">20.19. Tétel</a>) következménye a prímekre nézve. A másik összefüggés pedig a kínai maradéktétel (<a href="https://youproof.hu/kriptografia/22-kinai-maradektetel-konguenciarendszerek-kis-fermat-tetel-rsa-bizonyitas-gyuruk-direkt-szorzata-rsa-dekodolas/#yp-element-5934" class="yp-element-link">22.2. Tétel</a>), amely az úgynevezett kongruenciarendszerek megoldhatóságával, illetve a megoldások számával volt kapcsolatos. Végül egyrészt ennek következményeként egy – egyébként a számelmélet más területein is – rendkívül fontos gyűrűizomorfizmussal, másrészt a kis Fermat-tétel egy egyszerű következményével ismerkedtünk meg, amelyek együtt lehetővé teszik a kommunikáló felek számára az RSA-dekódolás felgyorsítását. De vajon hogyan képes Alice és Bob az RSA-kulcsgeneráláshoz szükséges többszázjegyű prímszámokat találni? Hogyan tudják ezt megtenni anélkül, hogy az idők végezetéig osztáspróbákat kellene végezniük? Mik azok a prímtesztek, és pontosan hogyan működnek? Mely számokat nevezzük univerzális álprímeknek, és hogyan tudunk megszabadulni tőlük? Ebben a részben erről lesz szó… Figyelem! Ez a rész erőteljesen épít a <a href="https://youproof.hu/kriptografia/16-oszhatosag-egyseg-asszocialt-felbonthatatlan-prim-szamelmelet-alaptetele/" target="_blank" rel="noreferrer noopener">16.</a>, <a href="https://youproof.hu/kriptografia/20-kongruencia-redukalt-maradekosztaly-euler-fuggveny-linearis-kongruencia-maradekrendszer-euler-fermat-tetel/" target="_blank" rel="noreferrer noopener">20.</a> és <a href="https://youproof.hu/kriptografia/22-kinai-maradektetel-konguenciarendszerek-kis-fermat-tetel-rsa-bizonyitas-gyuruk-direkt-szorzata-rsa-dekodolas/" target="_blank" rel="noreferrer noopener">22. részekben</a> felépített alábbi definíciókra, valamint a hozzájuk kapcsolódó tételekre:  <div class="yp-element-recall">  <div class="yp-element-expand-button yp-element-expand-button-inactive"> <div class="yp-element-expand-button-text">16.3. Definíció (Egység)</div> </div>  <div class="yp-element-recall-container">  <div class="yp-element-recall-content">  Legyen R egy tetszőleges kommutatív gyűrű. Ha egy adott e gyűrűelem esetén minden a gyűrűelemre teljesül az e|a oszthatósági reláció, akkor az e elemet egységnek nevezzük.  </div> <div class="yp-element-recall-links">   <a class="yp-element-link-to-article" href="https://youproof.hu/kriptografia/16-oszhatosag-egyseg-asszocialt-felbonthatatlan-prim-szamelmelet-alaptetele/#yp-element-3915" target="_blank">Kapcsolódó cikk</a> </div> </div> </div>  <div class="yp-element-recall">  <div class="yp-element-expand-button yp-element-expand-button-inactive"> <div class="yp-element-expand-button-text">16.6. Definíció (Asszociált)</div> </div>  <div class="yp-element-recall-container">  <div class="yp-element-recall-content">  Egy kommutatív gyűrű valamely a és b elemeire akkor mondjuk, hogy egymás asszociáltjai, ha pontosan ugyanazok a többszöröseik és az osztóik is. Pontosabban fogalmazva, ha tetszőleges r gyűrűelem esetén a|r akkor és csak akkor teljesül, amikor b|r is teljesül, valamint r|a akkor és csak akkor teljesül, amikor r|b is teljesül.   Azt, hogy a és b egymás asszociáltjai így jelöljük: a\sim b.  </div> <div class="yp-element-recall-links">   <a class="yp-element-link-to-article" href="https://youproof.hu/kriptografia/16-oszhatosag-egyseg-asszocialt-felbonthatatlan-prim-szamelmelet-alaptetele/#yp-element-3934" target="_blank">Kapcsolódó cikk</a> </div> </div> </div>  <div class="yp-element-recall">  <div class="yp-element-expand-button yp-element-expand-button-inactive"> <div class="yp-element-expand-button-text">16.11. Definíció (Felbonthatatlan elem)</div> </div>  <div class="yp-element-recall-container">  <div class="yp-element-recall-content">  Legyen R egy tetszőleges kommutatív gyűrű. Ha valamely a, b és c elemekre a=b\cdot c teljesül, akkor a b\cdot c szorzatot az a elem felbontásának nevezzük. Azokat a felbontásokat, amelyekben b és c közül az egyik egység, a másik pedig a asszociáltja, triviális felbontásoknak nevezzük. Ha egy gyűrűelem saját maga nem egység és nem létezik nemtriviális felbontása (azaz ha létezik is felbontása, az csak triviális lehet), akkor őt felbonthatatlannak vagy irreducibilisnek nevezzük. Ha egy elem nem felbonthatatlan és nem egység, akkor őt összetett elemnek nevezzük. Az egységeket nem tekintjük sem felbonthatatlannak, sem pedig összetettnek.  </div> <div class="yp-element-recall-links">   <a class="yp-element-link-to-article" href="https://youproof.hu/kriptografia/16-oszhatosag-egyseg-asszocialt-felbonthatatlan-prim-szamelmelet-alaptetele/#yp-element-4039" target="_blank">Kapcsolódó cikk</a> </div> </div> </div>  <div class="yp-element-recall">  <div class="yp-element-expand-button yp-element-expand-button-inactive"> <div class="yp-element-expand-button-text">16.13. Definíció (Prímtulajdonságú elem)</div> </div>  <div class="yp-element-recall-container">  <div class="yp-element-recall-content">  Egy R kommutatív gyűrű valamely p elemét prímtulajdonságú elemnek (vagy egyszerűen csak prímnek) nevezzük, ha nem a nullelem, nem egység, és csak úgy lehet osztója két gyűrűelem szorzatának, ha legalább az egyik tényezőnek osztója. Azaz ha valamely a és b gyűrűelemekre teljesül a p|ab oszthatóság, akkor a p|a vagy p|b oszthatóságok közül legalább az egyik ugyancsak teljesül.  </div> <div class="yp-element-recall-links">   <a class="yp-element-link-to-article" href="https://youproof.hu/kriptografia/16-oszhatosag-egyseg-asszocialt-felbonthatatlan-prim-szamelmelet-alaptetele/#yp-element-4064" target="_blank">Kapcsolódó cikk</a> </div> </div> </div>  <div class="yp-element-recall">  <div class="yp-element-expand-button yp-element-expand-button-inactive"> <div class="yp-element-expand-button-text">20.6. Definíció (Redukált maradékosztály)</div> </div>  <div class="yp-element-recall-container">  <div class="yp-element-recall-content">  Legyen m\gt 0 egy tetszőleges pozitív egész szám. Ekkor a \Z/m\Z-vel jelölt modulo m maradékosztálygyűrű (lásd a <a href="https://youproof.hu/kriptografia/20-kongruencia-redukalt-maradekosztaly-euler-fuggveny-linearis-kongruencia-maradekrendszer-euler-fermat-tetel/#yp-element-5352" class="yp-element-link">20.5. Tétel</a>t) invertálható elemeit modulo m redukált maradékosztályoknak nevezzük.  </div> <div class="yp-element-recall-links">   <a class="yp-element-link-to-article" href="https://youproof.hu/kriptografia/20-kongruencia-redukalt-maradekosztaly-euler-fuggveny-linearis-kongruencia-maradekrendszer-euler-fermat-tetel/#yp-element-5370" target="_blank">Kapcsolódó cikk</a> </div> </div> </div>  <div class="yp-element-recall">  <div class="yp-element-expand-button yp-element-expand-button-inactive"> <div class="yp-element-expand-button-text">20.7. Definíció (Az Euler-függvény)</div> </div>  <div class="yp-element-recall-container">  <div class="yp-element-recall-content">  Legyen m\gt 0 tetszőleges pozitív egész szám. Ekkor a modulo m redukált maradékosztályok számát a \varphi(m)-mel jelölt függvény értéke adja meg. Ezt a függvényt Euler-féle \varphi-függvénynek (ejtsd: „fi”) nevezzük.  </div> <div class="yp-element-recall-links">   <a class="yp-element-link-to-article" href="https://youproof.hu/kriptografia/20-kongruencia-redukalt-maradekosztaly-euler-fuggveny-linearis-kongruencia-maradekrendszer-euler-fermat-tetel/#yp-element-5378" target="_blank">Kapcsolódó cikk</a> </div> </div> </div>  <div class="yp-element-recall">  <div class="yp-element-expand-button yp-element-expand-button-inactive"> <div class="yp-element-expand-button-text">22.1. Tétel (A kis Fermat-tétel)</div> </div>  <div class="yp-element-recall-container">  <div class="yp-element-recall-content">  Legyen p\gt 0 egy tetszőleges pozitív prím, továbbá a egy tetszőleges egész szám, amely relatív prím p-hez. Ekkor teljesül az alábbi kongruencia:   a^{p-1}\equiv 1\pmod p   Az alábbi kongruencia tetszőleges a egész számra – tehát nem csak a p-hez relatív prímekre – teljesül:   a^p\equiv a\pmod p    </div> <div class="yp-element-recall-links">   <a class="yp-element-link-to-article" href="https://youproof.hu/kriptografia/22-kinai-maradektetel-konguenciarendszerek-kis-fermat-tetel-rsa-bizonyitas-gyuruk-direkt-szorzata-rsa-dekodolas/#yp-element-5892" target="_blank">Kapcsolódó cikk</a> </div> </div> </div>  <div class="yp-element-recall">  <div class="yp-element-expand-button yp-element-expand-button-inactive"> <div class="yp-element-expand-button-text">22.2. Tétel (Kínai maradéktétel)</div> </div>  <div class="yp-element-recall-container">  <div class="yp-element-recall-content">  Legyen a és b tetszőleges, p\gt 0 és q\gt 0 pedig valamilyen pozitív egész számok. Tegyük fel továbbá, hogy p és q egymáshoz relatív prímek. Ekkor az alábbi kongruenciarendszer megoldható, és a megoldás egyetlen modulo pq maradékosztály lesz:   \begin{aligned}x&\equiv a\pmod p \\ x&\equiv b\pmod q\end{aligned}   Más megfogalmazásban minden, a fenti két kongruenciát egyszerre kielégítő egész szám ugyanabba az egyetlen modulo pq maradékosztályba esik, továbbá ennek a bizonyos maradékosztálynak minden eleme kielégíti a fenti két kongruenciát.  </div> <div class="yp-element-recall-links">   <a class="yp-element-link-to-article" href="https://youproof.hu/kriptografia/22-kinai-maradektetel-konguenciarendszerek-kis-fermat-tetel-rsa-bizonyitas-gyuruk-direkt-szorzata-rsa-dekodolas/#yp-element-5934" target="_blank">Kapcsolódó cikk</a> </div> </div> </div> Ezek kontextusba helyezése miatt erőteljesen ajánlott elolvasni a <a rel="noreferrer noopener" href="https://youproof.hu/kriptografia/16-oszhatosag-egyseg-asszocialt-felbonthatatlan-prim-szamelmelet-alaptetele/" target="_blank">16.</a>, <a rel="noreferrer noopener" href="https://youproof.hu/kriptografia/20-kongruencia-redukalt-maradekosztaly-euler-fuggveny-linearis-kongruencia-maradekrendszer-euler-fermat-tetel/" target="_blank">20.</a> és <a rel="noreferrer noopener" href="https://youproof.hu/kriptografia/22-kinai-maradektetel-konguenciarendszerek-kis-fermat-tetel-rsa-bizonyitas-gyuruk-direkt-szorzata-rsa-dekodolas/" target="_blank">22. részeket</a>, mivel gyakran hivatkozni fogunk rájuk. A teljes cikksorozat elejét <a rel="noreferrer noopener" href="https://youproof.hu/kriptografia/1-alapfogalmak-caesar-vigenere-enigma-kulcsmegosztas/" target="_blank">itt</a> találod. Alice és Bob tehát ott ülnek az RSA-algoritmus <a rel="noreferrer noopener" href="https://youproof.hu/kriptografia/21-rsa-algoritmus-kibovitett-euklideszi-algoritmus-euler-fuggveny-kulcsgeneralas-ismetelt-negyzetreemeles-modszere#rsa" target="_blank">21. részben</a> ismertetett leírása felett, és mindketten szeretnének maguknak egy-egy kulcspárt generálni. Ezután ezek publikus részeit megosztják majd egymással, és indulhat a biztonságos kommunikáció, azaz mindenki boldog. Igenám, csakhogy a kulcsgenerálási eljárás első lépéseként először is mindkettejüknek kellene találnia két-két többszázjegyű prímszámot. Azt a <a href="https://youproof.hu/kriptografia/16-oszhatosag-egyseg-asszocialt-felbonthatatlan-prim-szamelmelet-alaptetele/#yp-element-4075" class="yp-element-link">16.14. Tétel</a> és a <a href="https://youproof.hu/kriptografia/17-euklideszi-algoritmus-maradekos-osztas-legnagyobb-kozos-oszto-euklideszi-gyuru/#yp-element-4246" class="yp-element-link">17.12. Tétel</a> következményeként tudják, hogy az egész számok \Z gyűrűjében a prímszámok (<a href="https://youproof.hu/kriptografia/16-oszhatosag-egyseg-asszocialt-felbonthatatlan-prim-szamelmelet-alaptetele/#yp-element-4064" class="yp-element-link">16.13. Definíció</a>) és felbonthatatlan számok (<a href="https://youproof.hu/kriptografia/16-oszhatosag-egyseg-asszocialt-felbonthatatlan-prim-szamelmelet-alaptetele/#yp-element-4039" class="yp-element-link">16.11. Definíció</a>) köre éppenséggel egybeesik. Emiatt a továbbiakban ezt a két – egyébként teljesen különböző – gyűrűelméleti fogalmat egymás szinonímájaként fogjuk használni. A prímszámok keresése szempontjából lényeges kérdés, hogy azok mennyire gyakran fordulnak elő ebben a számtartományban. Az úgynevezett prímszámláló függvény egy olyan függvény, amely azt adja meg bármilyen n pozitív egészre, hogy mennyi az n-nél nemnagyobb pozitív prímek száma. Ezt a függvényt \pi-vel jelöljük. Az alábbiakban a prímszámláló függvény értékét láthatjuk néhány pozitív egész számra: \begin{aligned}\pi(1)&=0 \\ \pi(2)&=1 \\ \pi(3)&=2 \\ \pi(3)&=2 \\ \pi(10)&=4 \\ \pi(100)&=25 \\ \pi(1000000)&=78498 \\ &\vdots \end{aligned} Az alábbi ábrán pedig a függvény grafikonja látható az első 60 pozitív egész számra: <div class="wp-block-image"><figure class="aligncenter size-large"><img decoding="async" width="300" height="238" src="https://youproof.hu/wp-content/uploads/kriptografia_23_primszamlalo_fuggveny_grafikon.jpg" alt="Prímszámláló függvény" class="wp-image-6444"/><figcaption>Prímszámláló függvény</figcaption></figure></div> Sajnos a prímszámláló függvényre nincs képletünk, amelybe tetszőleges pozitív egész számot behelyettesítve varázslatos módon megkaphatnánk az értékét. Azonban az úgynevezett analitikus számelmélet egy nevezetes tétele szerint ez az érték viszonylag jól becsülhető egy másik, könnyen kiszámítható függvénnyel. Ez <a rel="noreferrer noopener" href="https://en.wikipedia.org/wiki/Prime_number_theorem" target="_blank">„nagy prímszámtétel”</a> néven ismeretes, amelynek részleteire ebben a cikksorozatban nem térünk ki. Ez alapján kiszámítható, hogy a 300-600 számjegyből álló számok tartományában – amelyben Alice és Bob-nak prímeket kéne keresnie az RSA-kulcsokhoz – hogyan alakul a prímek eloszlása. Eszerint ha Alice és Bob teljesen véletlenszerűen kisorsol számokat ebből a tartományból, akkor nagyjából minden párszázadik próbálkozásnál belebotlanak egy-egy prímszámba. Így már csak az a kérdés, hogy Alice és Bob hogyan tudja gyorsan eldönteni egy konkrét egész számról, hogy prím-e vagy sem. Az erre szolgáló algoritmusokat prímteszteknek nevezzük. A most következő prímtesztelő eljárás ismerős lehet az általános iskolából is. <h4 class="wp-block-heading" id="naive-primality-test">Prímtesztelés osztáspróbákkal</h4> Alice és Bob némi gondolkodás után néhány korábbi részben ismertetett összefüggés alapján az alábbi egyszerű, és mindenki számára jól ismert következtetésre jut a prímszámokkal kapcsolatban.  <div class="yp-element-normal" id="yp-element-6217">  <h4 class="yp-element-indexed-header">23.1. Tétel:</h4>    Legyen n\neq 0 egy tetszőleges nemnulla egész szám, amely nem egység. Ebben az esetben n akkor és csak akkor prím (azaz felbonthatatlan), ha nem létezik 1-nél nagyobb, de |n|-nél kisebb osztója.   Ezzel ekvivalens megfogalmazás: Az n akkor és csak akkor összetett (tehát nem prím, azaz nem felbonthatatlan), ha létezik 1-nél nagyobb, de |n|-nél kisebb osztója.   Itt |n| jelöli az n egész szám <a href="https://youproof.hu/kriptografia/17-euklideszi-algoritmus-maradekos-osztas-legnagyobb-kozos-oszto-euklideszi-gyuru/#yp-element-4359" class="yp-element-link">17.18. Definíció</a> szerinti abszolútértékét.   ♣</div>  <div class="yp-element-normal" id="yp-element-6219">  <h4 class="yp-element-non-indexed-header">Bizonyítás:</h4>    Először nézzük azt az esetet, amikor n pozitív, azaz n\gt 0. Ekkor ugye |n|=n a <a href="https://youproof.hu/kriptografia/17-euklideszi-algoritmus-maradekos-osztas-legnagyobb-kozos-oszto-euklideszi-gyuru/#yp-element-4359" class="yp-element-link">17.18. Definíció</a> alapján.   Tegyük fel, hogy n-nek létezik 1-nél nagyobb, de |n|=n-nél kisebb osztója, amit jelöljünk k-val. Azaz egyrészt:   1\lt k\lt n   Másrészt:   k|n   Ez az oszthatóság a <a href="https://youproof.hu/kriptografia/16-oszhatosag-egyseg-asszocialt-felbonthatatlan-prim-szamelmelet-alaptetele/#yp-element-3866" class="yp-element-link">16.1. Definíció</a> alapján azt jelenti, hogy létezik olyan l egész szám, hogy teljesül az alábbi egyenlet:   n=k\cdot l   A felbonthatatlanság <a href="https://youproof.hu/kriptografia/16-oszhatosag-egyseg-asszocialt-felbonthatatlan-prim-szamelmelet-alaptetele/#yp-element-4039" class="yp-element-link">16.11. Definíció</a>ja alapján azt kell bizonyítani, hogy ez a szorzat n-nek egy nemtriviális felbontása, azaz sem k, sem pedig l nem egység, és nem is asszociáltja n-nek.   Egyrészt a <a href="https://youproof.hu/kriptografia/16-oszhatosag-egyseg-asszocialt-felbonthatatlan-prim-szamelmelet-alaptetele/#yp-element-3928" class="yp-element-link">16.5. Tétel</a> alapján az egész számok \Z gyűrűjében az 1-en és a -1-en kívül nincs más egység. Mivel 1 pozitív, ezért a <a href="https://youproof.hu/kriptografia/15-rendezett-gyuru-absztrakt-algebra-egesz-szam-rendezesi-relacio-rendezesi-axiomak/#yp-element-3672" class="yp-element-link">15.12. Definíció</a> utáni megjegyzés alapján -1 negatív. Emiatt k biztosan nem lehet egység, hiszen ő maga pozitív, továbbá határozottan nagyobb 1-nél.   Másrészt a <a href="https://youproof.hu/kriptografia/16-oszhatosag-egyseg-asszocialt-felbonthatatlan-prim-szamelmelet-alaptetele/#yp-element-3996" class="yp-element-link">16.10. Tétel</a> alapján n-nek mindössze két asszociáltja van, méghozzá önmaga, és az ellentettje, azaz -n. Mivel n pozitív, ezért a <a href="https://youproof.hu/kriptografia/15-rendezett-gyuru-absztrakt-algebra-egesz-szam-rendezesi-relacio-rendezesi-axiomak/#yp-element-3672" class="yp-element-link">15.12. Definíció</a> utáni megjegyzés alapján -n negatív. Emiatt viszont k biztosan nem lehet n asszociáltja sem, hiszen ő maga pozitív, továbbá határozottan kisebb n-nél.   A k egész szám tehát egy olyan osztója n-nek, amely se nem egység, se nem asszociáltja n-nek. Most ugyanezt kellene megmutatni a fenti szorzat másik tényezőjéről, azaz l-ről is. Ez viszont automatikusan teljesül a <a href="https://youproof.hu/kriptografia/16-oszhatosag-egyseg-asszocialt-felbonthatatlan-prim-szamelmelet-alaptetele/#yp-element-4053" class="yp-element-link">16.12. Tétel</a> miatt. Ha ugyanis l egység lenne, akkor ez alapján k szükségképpen n-nek asszociáltja lenne. Ha viszont l asszociáltja lenne n-nek, akkor k szükségképpen egység lenne. Mindkét esetről láttuk, hogy nem ez a helyzet.   Megtaláltuk tehát n-nek egy nemtriviális felbontását, így ő a <a href="https://youproof.hu/kriptografia/16-oszhatosag-egyseg-asszocialt-felbonthatatlan-prim-szamelmelet-alaptetele/#yp-element-4039" class="yp-element-link">16.11. Definíció</a> alapján valóban összetett.   Visszafelé: Tegyük most fel indirekt, hogy n összetett ugyan, ám mégsem létezik olyan osztója, amely 1-nél nagyobb, de |n|=n-nél kisebb. Mivel összetett, így a <a href="https://youproof.hu/kriptografia/16-oszhatosag-egyseg-asszocialt-felbonthatatlan-prim-szamelmelet-alaptetele/#yp-element-4039" class="yp-element-link">16.11. Definíció</a> alapján létezik valamilyen nemtriviális felbontása. Például:   n=k\cdot l   Egyrészt, mivel n\neq 0, ezért a <a href="https://youproof.hu/kriptografia/16-oszhatosag-egyseg-asszocialt-felbonthatatlan-prim-szamelmelet-alaptetele/#yp-element-3894" class="yp-element-link">16.2. Tétel</a> 4. pontja alapján k és l egyike sem lehet 0. Másrészt, mivel a fenti felbontás ugye nemtriviális, ezért egyikük sem lehet egység, továbbá egyikük sem lehet asszociáltja n-nek. Harmadrészt, indirekt feltevésünk miatt egyikük sem eshet az 1 és az |n|=n közötti számtartományba. Végül negyedrészt a <a href="https://youproof.hu/kriptografia/17-euklideszi-algoritmus-maradekos-osztas-legnagyobb-kozos-oszto-euklideszi-gyuru/#yp-element-4180" class="yp-element-link">17.2. Lemma</a> alapján egyikük sem lehet nagyobb n-nél. Összefoglalva tehát k és l mindketten negatívak, határozottan kisebbek -1-nél, továbbá -n-től különbözőek. Ezt mutatja az alábbi ábra:   <div class="wp-block-image"><figure class="aligncenter size-large"><img loading="lazy" decoding="async" width="300" height="77" src="https://youproof.hu/wp-content/uploads/kriptografia_23_osztok_elhelyezkedese_2.jpg" alt="Osztók elhelyezkedése" class="wp-image-6468"/><figcaption>Osztók elhelyezkedése</figcaption></figure></div>   Az n=k\cdot l egyenlet miatt azonban a <a href="https://youproof.hu/kriptografia/15-rendezett-gyuru-absztrakt-algebra-egesz-szam-rendezesi-relacio-rendezesi-axiomak/#yp-element-3576" class="yp-element-link">15.1. Tétel</a> 4. pontja alapján teljesül az alábbi egyenlet is:   n=(-k)\cdot (-l)   A k és l egész számok ellentettjei tehát szintén osztói n-nek, mindketten pozitívak, határozottan nagyobbak 1-nél, továbbá n-től különbözőek. Ezt az alábbi ábra mutatja:   <div class="wp-block-image"><figure class="aligncenter size-large"><img loading="lazy" decoding="async" width="300" height="80" src="https://youproof.hu/wp-content/uploads/kriptografia_23_osztok_elhelyezkedese_1.jpg" alt="Osztók ellentettjeinek elhelyezkedése" class="wp-image-6469"/><figcaption>Osztók ellentettjeinek elhelyezkedése</figcaption></figure></div>   A <a href="https://youproof.hu/kriptografia/17-euklideszi-algoritmus-maradekos-osztas-legnagyobb-kozos-oszto-euklideszi-gyuru/#yp-element-4180" class="yp-element-link">17.2. Lemma</a> miatt az n-nél nagyobb számtartományt ismételten kizárhatjuk. Így végülis indirekt feltételezésünkkel ellentétben mégiscsak találtunk két olyan osztót – nevezetesen a -k és -l egész számokat –, amelyek 1-nél nagyobbak, de |n|=n-nél kisebbek.   Végezetül nézzük most azt az esetet, amikor n negatív, azaz n\lt 0. Ekkor egyrészt a <a href="https://youproof.hu/kriptografia/15-rendezett-gyuru-absztrakt-algebra-egesz-szam-rendezesi-relacio-rendezesi-axiomak/#yp-element-3672" class="yp-element-link">15.12. Definíció</a> utáni megjegyzés alapján -n pozitív. Másrészt pedig a <a href="https://youproof.hu/kriptografia/16-oszhatosag-egyseg-asszocialt-felbonthatatlan-prim-szamelmelet-alaptetele/#yp-element-3980" class="yp-element-link">16.8. Tétel</a> 1. pontja alapján ő n-nek asszociáltja, azaz pontosan ugyanazok az osztói, mint n-nek. Így n akkor és csak akkor prím, ha -n is, amelyre viszont pozitivitása miatt szóról szóra alkalmazható a fenti gondolatmenet.   ∎</div> Ez alapján tehát egy adott n egész szám esetén elegendő osztáspróbákkal ellenőrizni, hogy teljesül-e valamelyik oszthatóság az alábbiak közül: \begin{aligned}2&|n \\ 3&|n \\ 4&|n \\ &\vdots \\ |n|-1&|n\end{aligned} Ha ezek közül akárcsak egyetlen oszthatóság is teljesül, akkor az iménti tétel alapján a prímtesztelő algoritmus leállhat azzal a válasszal, hogy n „biztosan összetett”. Ezzel szemben ha egyetlen oszthatóság sem teljesül a fentiek közül, akkor ugyancsak a fenti tétel alapján n „biztosan prím”. Például az n=7 „biztosan prím”, hiszen: \begin{aligned}2&\nmid 7 \\ 3&\nmid 7 \\ 4&\nmid 7 \\ 5&\nmid 7 \\ 6&\nmid 7\end{aligned} Ezzel szemben az n=35 „biztosan összetett”, hiszen: \begin{aligned}2&\nmid 35 \\ 3&\nmid 35 \\ 4&\nmid 35 \\ 5&|35\end{aligned} Főhőseink tehát ez alapján bármilyen egész számról el tudják dönteni, hogy prímszám-e vagy sem. Csakhogy van egy kis probléma ezzel az eljárással, amely akkor jelentkezik, amikor a gyakorlatban előforduló nagyságrendű számokra kezdjük el lefuttatni. Vizsgáljuk ezért meg, hogy mekkora az eljárás számításigénye a bemenet méretének függvényében. A „bemenet mérete” alatt itt értelemszerűen a leírásához szükséges számjegyek számát fogjuk érteni. Jelöljük ezt a számot mondjuk k-val, és tegyük fel, hogy tizes számrendszerben dolgozunk. A lehető legkisebb k számjegyből álló egész szám a 10^{k-1} lesz. Vagyis ha a bemenet történetesen prímszám, akkor ez nagyságrendileg legalább ennyi osztáspróba után fog csak kiderülni. Ez bizony a bemenet méretének exponenciális függvénye, és így az algoritmus sajnos a <a rel="noreferrer noopener" href="https://youproof.hu/kriptografia/7-algoritmus-bonyolultsag-problemaosztalyok-polinomialis-exponencialis-p-np-sejtes-tanu-tetel#algorithm-time-complexity" target="_blank">7. részben</a> tanultak alapján nem nevezhető hatékonynak. Nem sokkal jobb a helyzet akkor sem, ha a bemenet összetett szám, kivéve persze az olyan ritka eseteket, amikor viszonylag kicsi prímtényezője is van. A <a rel="noreferrer noopener" href="https://youproof.hu/kriptografia/21-rsa-algoritmus-kibovitett-euklideszi-algoritmus-euler-fuggveny-kulcsgeneralas-ismetelt-negyzetreemeles-modszere#rsa" target="_blank">21. részben</a> már említettük, hogy az RSA esetén manapság tipikusan 300-600 számjegyből álló prímszámokat használnak, ezért az algoritmus futása ebben a számtartományban az idők végezetéig is eltarthat, és így a gyakorlatban nem használható. Alice és Bob tehát tovább töri a fejét, hogyan tudnának ennél jóval kevesebb osztáspróbával is célt érni, és némi gondolkodás után az alábbi következtetésre jutnak.  <div class="yp-element-normal" id="yp-element-6234">  <h4 class="yp-element-indexed-header">23.2. Tétel:</h4>    Legyen n\neq 0 egy tetszőleges nemnulla egész szám, amely nem egység, valamint jelöljük r-rel a lehető legnagyobb olyan egész számot, amelyre r^2\leq |n| teljesül.   Ebben az esetben az n egész szám akkor és csak akkor prím (azaz felbonthatatlan), ha nem létezik olyan osztója, amely 1-nél nagyobb, de legfeljebb r.   Ezzel ekvivalens megfogalmazás: Az n egész szám akkor és csak akkor összetett (tehát nem prím, azaz nem felbonthatatlan), ha létezik olyan osztója, amely 1-nél nagyobb, de legfeljebb r.   ♣</div>  <div class="yp-element-normal" id="yp-element-6235">  <h4 class="yp-element-non-indexed-header">Bizonyítás:</h4>    Előszöris az világos, hogy r nemnegatív, hiszen az ő és az ellentettjének a négyzete megegyezik, így ha negatív lenne, akkor nem ő lenne a legnagyobb olyan egész szám, amelyre r^2\leq |n| teljesül.   Másodszor r biztosan nem lehet nulla sem. A <a href="https://youproof.hu/kriptografia/17-euklideszi-algoritmus-maradekos-osztas-legnagyobb-kozos-oszto-euklideszi-gyuru/#yp-element-4365" class="yp-element-link">17.19. Tétel</a> alapján ugyanis az abszolútérték-függvény egy euklidészi norma az egész számok \Z gyűrűjén, és így a <a href="https://youproof.hu/kriptografia/17-euklideszi-algoritmus-maradekos-osztas-legnagyobb-kozos-oszto-euklideszi-gyuru/#yp-element-4316" class="yp-element-link">17.16. Definíció</a> 1. pontja alapján n\neq 0-ból |n|\neq 0, azaz végülis 1\leq |n| következik. Ha mármost r nulla lenne, akkor igaz ugyan, hogy a négyzete nem haladná meg |n|-t, ám ekkor lenne nála nagyobb ugyanilyen tulajdonságú szám is (például az 1).   Összefoglalva r-re teljesülni fog az 1\leq r egyenlőtlenség, ebből pedig a <a href="https://youproof.hu/kriptografia/15-rendezett-gyuru-absztrakt-algebra-egesz-szam-rendezesi-relacio-rendezesi-axiomak/#yp-element-3659" class="yp-element-link">15.11. Definíció</a>ban ismertetett 2. rendezési axióma alapján r\leq r^2 következik. Ezt összevetve a tétel szövegében szereplő r^2\leq |n| feltétellel teljesül az alábbi:   1\leq r\leq |n|   Ennyi előkészület után igazoljuk a tétel állítását. Tegyük fel, hogy n prím. Ekkor a <a href="https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/#yp-element-6217" class="yp-element-link">23.1. Tétel</a> alapján egyáltalán nincsen osztója 1 és |n| között. Következésképp az ennél szűkebb, 1 és r közötti szakaszon „méginkább” nincs osztója.   Visszafelé: Először azt az esetet igazoljuk, amikoris n pozitív. Tegyük fel, hogy n összetett, azaz létezik valamilyen n=k\cdot l nemtriviális felbontása. Az általánosság megsértése nélkül feltehetjük, hogy k és l mindketten pozitívak, máskülönben ellentettjüket véve ez az állapot elérhető. Azt kell igazolni, hogy k és l közül legalább az egyik nemnagyobb r-nél. Tegyük fel indirekt, hogy nem ez a helyzet, vagyis az alábbi két eset valamelyike áll fenn:   \begin{aligned}r&\lt k\leq l \\ r&\lt l\leq k\end{aligned}   Első esetben a jobboldali egyenlőtlenség mindkét oldalát k-val megszorozva az alábbit kapjuk: k^2\leq k\cdot l=n. Ez viszont r\lt k miatt lehetetlen, hiszen a tétel szövege alapján r a legnagyobb olyan szám, amelynek négyzete |n|=n-t nem lépi túl.   Ehhez hasonlóan a második esetben a jobboldali egyenlőtlenség mindkét oldalát l-lel megszorozva ezt kapjuk: l^2\leq l\cdot k=n. Ez r\lt l miatt az előbb ismertetett okból szintén lehetetlen.   Indirekt feltételezésünk hibás volt, vagyis k és l közül az egyik biztosan nem lehet nagyobb r-nél, ahogyan a tétel állítja.   Végezetül nézzük most azt az esetet, amikor n negatív, azaz n\lt 0. Ekkor egyrészt a <a href="https://youproof.hu/kriptografia/15-rendezett-gyuru-absztrakt-algebra-egesz-szam-rendezesi-relacio-rendezesi-axiomak/#yp-element-3672" class="yp-element-link">15.12. Definíció</a> utáni megjegyzés alapján -n pozitív. Másrészt pedig a <a href="https://youproof.hu/kriptografia/16-oszhatosag-egyseg-asszocialt-felbonthatatlan-prim-szamelmelet-alaptetele/#yp-element-3980" class="yp-element-link">16.8. Tétel</a> 1. pontja alapján ő n-nek asszociáltja, azaz pontosan ugyanazok az osztói, mint n-nek. Így n akkor és csak akkor prím, ha -n is, amelyre viszont pozitivitása miatt szóról szóra alkalmazható a fenti gondolatmenet.   ∎</div> Ez alapján tehát az osztáspróbákkal elegendő addig a számig elmenni, amelynek a négyzete még épp |n| alatt marad. Ha eddig nem találunk osztót, akkor ezután sem fogunk. Például az n=61 „biztosan prím”, hiszen: \begin{aligned}2&\nmid 61 \\ 3&\nmid 61 \\ 4&\nmid 61 \\ 5&\nmid 61 \\ 6&\nmid 61 \\ 7&\nmid 61\end{aligned} A további osztáspróbákat már nem érdemes elvégezni, hiszen 8 négyzetével már túllépnénk a 61-et, így ha 7-ig bezárólag nincs osztója a 61-nek, akkor 7-nél nagyobb osztója sem lesz. Ez első látásra lényeges gyorsításnak tűnik, de sajnos nem az. Most nem teljes matematikai precizitással felvázoljuk, hogy miért. Tegyük fel ismét, hogy a bemeneti szám k darab számjegyből áll, és tizes számrendszerben dolgozunk. A lehető legkisebb k számjegyből álló szám a 10^{k-1}. Egy ekkora számnak a teszteléséhez az iménti tétel alapján nagyságrendileg r darab osztáspróbát kell elvégezni, ahol r a legnagyobb olyan szám, amelyre teljesül, hogy r^2\leq 10^{k-1}. Tegyük fel, hogy r a tizes számrendszerben l darab számjeggyel írható le, azaz r legalább 10^{l-1}. Ezt négyzetre emelve azt kapjuk, hogy r^2 legalább 10^{2\cdot (l-1)}. Összefoglalva: 10^{2\cdot (l-1)} \leq r^2 \leq 10^{k-1} Azaz: 10^{l-1} \leq r \leq 10^{\frac{k-1}{2}} Ez az exponenciális függvény tulajdonságai miatt azt jelenti, hogy r felírásához legalább feleannyi számjegy kell, mint ahány számjegyből a bemeneti szám áll. Mivel r az elvégzendő osztáspróbák számát jelenti, ezért ez sajnos még mindig a bemenet méretének exponenciális függvénye. Alice és Bob tehát továbbra sem mennek sokra ezzel a prímtesztelési eljárással abban a számtartományban, ahol prímszámokat szeretnének keresni. Ezért most szintet lépünk, és egy lényegesen más elven működő prímtesztet ismertetünk. <div id="fermat-primality-test"></div> <h4 class="wp-block-heading">A Fermat-prímteszt</h4> Ennek a prímtesztelő eljárásnak az alapja az <a rel="noreferrer noopener" href="https://youproof.hu/kriptografia/22-kinai-maradektetel-konguenciarendszerek-kis-fermat-tetel-rsa-bizonyitas-gyuruk-direkt-szorzata-rsa-dekodolas/" target="_blank">előző részben</a> megismert kis Fermat-tétel. Ez a tétel azt állítja, hogy HA egy n\gt 0 pozitív egész szám prímszám, AKKOR minden n-hez relatív prím a egész szám esetén teljesülni fog az alábbi kongruencia: a^{n-1} \equiv 1 \pmod n Más megfogalmazásban azt is mondhatjuk, hogy amennyiben akárcsak egyetlen olyan n-hez relatív prím a egész szám is létezik, amelyre nem teljesül a fenti kongruencia, akkor n biztosan nem prím (azaz összetett, vagy egység). Egy ilyen a egész szám tehát „leleplezi” vagy „tanúsítja” n összetettségét. Könnyen adódik, hogyha egy a egész szám tanú a fenti értelemben, akkor minden olyan b egész szám is tanú, amely a-val azonos modulo n maradékosztályban van. Ekkor ugyanis teljesül az a\equiv b\pmod n kongruencia, és így a <a href="https://youproof.hu/kriptografia/20-kongruencia-redukalt-maradekosztaly-euler-fuggveny-linearis-kongruencia-maradekrendszer-euler-fermat-tetel/#yp-element-5263" class="yp-element-link">20.2. Tétel</a> 8. pontja miatt teljesül az alábbi kongruencia is: a^{n-1} \equiv b^{n-1} \pmod n Mármost ha a baloldal nem kongruens 1-gyel – azaz a tanú –, akkor a jobboldal sem lehet kongruens 1-gyel – azaz b is tanú. Az alábbi definícióban tehát a fenti értelemben vett „tanú” fogalmát praktikus módon komplett maradékosztályokra vonatkoztatjuk.  <div class="yp-element-normal" id="yp-element-6264">  <h4 class="yp-element-indexed-header">23.3. Definíció (Fermat-tanú):</h4>    Legyen n\gt 1 egy tetszőleges pozitív, a pedig tetszőleges egész szám, amely nem többszöröse n-nek, azaz n\nmid a. Tegyük fel továbbá, hogy nem teljesül a kis Fermat-tételben (<a href="https://youproof.hu/kriptografia/22-kinai-maradektetel-konguenciarendszerek-kis-fermat-tetel-rsa-bizonyitas-gyuruk-direkt-szorzata-rsa-dekodolas/#yp-element-5892" class="yp-element-link">22.1. Tétel</a>) szereplő kongruencia, azaz:   a^{n-1} \ \cancel{\equiv} \ 1 \pmod n   Ekkor az a egész szám által reprezentált [a]_n maradékosztályt az n egész szám Fermat-tanújának nevezzük.   ♣</div>  <div class="yp-element-normal" id="yp-element-6304">  <h4 class="yp-element-non-indexed-header">Megjegyzés:</h4>    A definícióban nem kell külön kikötni, hogy a és n legyen relatív prím – ami a <a href="https://youproof.hu/kriptografia/20-kongruencia-redukalt-maradekosztaly-euler-fuggveny-linearis-kongruencia-maradekrendszer-euler-fermat-tetel/#yp-element-5482" class="yp-element-link">20.14. Tétel</a> értelmében azt jelentené, hogy [a]_n egy redukált maradékosztály –, hiszen ha nem ez lenne a helyzet, akkor az szintén tanúsítaná n összetettségét. Ez ugyanis egyrészt azt jelentené, hogy az (a,n) kitüntetett közös osztó különbözne az egységektől. Másrészt az n\nmid a feltételből az is következik, hogy ez a közös osztó n-től – és így n asszociáltjaitól – is különbözne. Ez nyilvánvaló is, hiszen (a,n)=n azt jelentené, hogy mégiscsak teljesül az n|a oszthatóság. Mármost ha az (a,n) kitüntetett közös osztó egyben n-nek is osztója, akkor n-nek lenne az egységektől és a saját asszociáltjaitól különböző osztója is, azaz nem lehetne prím.   Nem mellesleg megjegyezzük, hogy az a^{n-1}\equiv 1\pmod n kongruencia a <a href="https://youproof.hu/kriptografia/20-kongruencia-redukalt-maradekosztaly-euler-fuggveny-linearis-kongruencia-maradekrendszer-euler-fermat-tetel/#yp-element-6746" class="yp-element-link">20.20. Tétel</a> értelmében amúgysem teljesülhetne, amennyiben [a]_n nem egy redukált maradékosztály, azaz (a,n)\neq 1. Ez tehát azt jelenti, hogy NEM Fermat-tanú csak redukált maradékosztály lehet. Az alábbi ábrán ezek elhelyezkedése látható az összes modulo n maradékosztályok között. Az összes többi maradékosztály Fermat-tanú, ami ezen a halmazon kívül van – kivéve persze a [0]_n maradékosztályt.   <div class="wp-block-image"><figure class="aligncenter size-large"><img loading="lazy" decoding="async" width="300" height="261" src="https://youproof.hu/wp-content/uploads/kriptografia_23_nem_fermat_tanuk_elhelyezkedese.jpg" alt="A nem Fermat-tanúk elhelyezkedése" class="wp-image-6470"/><figcaption>A nem Fermat-tanúk elhelyezkedése</figcaption></figure></div>   ♣</div> A kis Fermat-tétel eszerint úgy is megfogalmazható, hogy amennyiben egy n egész számnak létezik Fermat-tanúja, akkor „biztosan összetett”. Így ha n-ről szeretnénk eldönteni, hogy prím-e, akkor nincs más dolgunk, mint keresni egy Fermat-tanút a nemnulla modulo n maradékosztályok között. Igenám, csakhogy e maradékosztályok száma borzasztóan nagy – egészen pontosan n-1 –, így reménytelennek tűnik bármiféle ezek között való keresgélés. Az az érdekes, hogy ennek ellenére viszonylag gyorsan tudunk Fermat-tanút találni, amennyiben egyáltalán létezik ilyen. Most ennek okát fogjuk megvizsgálni. Az alábbi táblázatban néhány adatot láthatunk az összes 500 és 600 közötti páratlan számról. A táblázat első oszlopa magát a vizsgált n számot tartalmazza. A második oszlopban azt láthatjuk, hogy összesen hány modulo n redukált maradékosztály létezik. Ez tehát a <a href="https://youproof.hu/kriptografia/20-kongruencia-redukalt-maradekosztaly-euler-fuggveny-linearis-kongruencia-maradekrendszer-euler-fermat-tetel/#yp-element-5378" class="yp-element-link">20.7. Definíció</a> alapján épp az Euler-féle \varphi-függvény értéke. A harmadik oszlop tartalmazza azt, hogy e \varphi(n) darab redukált maradékosztály között mennyi olyan van, amely nem Fermat-tanú. Ezt az értéket l(n)-nel jelöltük. Végül a negyedik oszlop azt tartalmazza, hogy n ténylegesen prím-e vagy sem: \begin{array}{c||c}\begin{array}{c|c|c|c} n & \varphi(n) & l(n) & \text{prím} \\ \hline 501 & 332 & 4 & \text{nem} \\ 503 & 502 & 502 & \text{igen} \\ 505 & 400 & 16 & \text{nem} \\ 507 & 312 & 4 & \text{nem} \\ 509 & 508 & 508 & \text{igen} \\ 511 & 432 & 36 & \text{nem} \\ 513 & 324 & 4 & \text{nem} \\ 515 & 408 & 4 & \text{nem} \\ 517 & 460 & 4 & \text{nem} \\ 519 & 344 & 4 & \text{nem} \\ 521 & 520 & 520 & \text{igen} \\ 523 & 522 & 522 & \text{igen} \\ 525 & 240 & 16 & \text{nem} \\ 527 & 480 & 4 & \text{nem} \\ 529 & 506 & 22 & \text{nem} \\ 531 & 348 & 4 & \text{nem} \\ 533 & 480 & 16 & \text{nem} \\ 535 & 424 & 4 & \text{nem} \\ 537 & 356 & 4 & \text{nem} \\ 539 & 420 & 4 & \text{nem} \\ 541 & 540 & 540 & \text{igen} \\ 543 & 360 & 4 & \text{nem} \\ 545 & 432 & 16 & \text{nem} \\ 547 & 546 & 546 & \text{igen} \\ 549 & 360 & 8 & \text{nem} \end{array} & \begin{array}{c|c|c|c} n & \varphi(n) & l(n) & \text{prím} \\ \hline 551 & 504 & 4 & \text{nem} \\ 553 & 468 & 36 & \text{nem} \\ 555 & 288 & 8 & \text{nem} \\ 557 & 556 & 556 & \text{igen} \\ 559 & 504 & 36 & \text{nem} \\ 561 & 320 & 320 & \boxed{\text{nem}} \\ 563 & 562 & 562 & \text{igen} \\ 565 & 448 & 16 & \text{nem} \\ 567 & 324 & 4 & \text{nem} \\ 569 & 568 & 568 & \text{igen} \\ 571 & 570 & 570 & \text{igen} \\ 573 & 380 & 4 & \text{nem} \\ 575 & 440 & 4 & \text{nem} \\ 577 & 576 & 576 & \text{igen} \\ 579 & 384 & 4 & \text{nem} \\ 581 & 492 & 4 & \text{nem} \\ 583 & 520 & 4 & \text{nem} \\ 585 & 288 & 32 & \text{nem} \\ 587 & 586 & 586 & \text{igen} \\ 589 & 540 & 36 & \text{nem} \\ 591 & 392 & 4 & \text{nem} \\ 593 & 592 & 592 & \text{igen} \\ 595 & 384 & 24 & \text{nem} \\ 597 & 396 & 4 & \text{nem} \\ 599 & 598 & 598 & \text{igen} \end{array} \end{array} A táblázatból legalábbis úgy tűnik, hogy amennyiben egy n egész szám összetett, akkor ezt rendkívül sok, sőt „majdnem mindegyik” modulo n redukált maradékosztály tanúsítja. Ez abból látszik, hogy az összetett számok esetén a táblázat harmadik oszlopában lévő szám nagyon kicsi. Az egyetlen kakukktojás ebben a számtartományban az 561, akire hamarosan visszatérünk még. Ez azt is jelenti, hogy véletlenszerűen választott redukált maradékosztályok vizsgálatával jó eséllyel nagyon hamar „leleplezhetjük” n-t, amennyiben összetett, hiszen kicsi az esélye, hogy épp a néhány nem Fermat-tanú valamelyikét választjuk. Ráadásul egy-egy ilyen vizsgálatot a <a rel="noreferrer noopener" href="https://youproof.hu/kriptografia/21-rsa-algoritmus-kibovitett-euklideszi-algoritmus-euler-fuggveny-kulcsgeneralas-ismetelt-negyzetreemeles-modszere#modular-exponentiation" target="_blank">21. részben</a> tanult ismételt négyzetreemelések módszerével rettentően hamar el is tudunk végezni. Hamarosan általánosságban is igazolni fogunk egy alsó becslést a Fermat-tanúk számára vonatkozóan. Ez ugyan jóval szerényebb lesz annál, mint ami a táblázatból látszik, ám egy hatékonyan működő prímteszthez még ez is bőven elég lesz. Ehhez azonban először két segédtételre lesz szükségünk. Az első arra vonatkozik, hogy egy Fermat-tanúból hogyan tudunk előállítani egy másik Fermat-tanút.  <div class="yp-element-normal" id="yp-element-6279">  <h4 class="yp-element-indexed-header">23.4. Lemma:</h4>    Legyen n\gt 1 tetszőleges pozitív egész szám. Tegyük fel, hogy adva van egy valamilyen a egész szám által reprezentált [a]_n redukált maradékosztály, amely Fermat-tanú. Legyen adott továbbá egy valamilyen b\neq 0 egész szám által reprezentált [b]_n redukált maradékosztály, amely nem Fermat-tanú.   Ekkor e két maradékosztály szorzata, vagyis az [a]_n \odot [b]_n maradékosztály egyrészt Fermat-tanú, másrészt szintén redukált maradékosztály.   Itt „szorzás” alatt a modulo n maradékosztálygyűrű \odot szimbólummal jelölt szorzás műveletét értjük (lásd a <a href="https://youproof.hu/kriptografia/20-kongruencia-redukalt-maradekosztaly-euler-fuggveny-linearis-kongruencia-maradekrendszer-euler-fermat-tetel/#yp-element-5352" class="yp-element-link">20.5. Tétel</a>t).   ♣</div>  <div class="yp-element-normal" id="yp-element-6280">  <h4 class="yp-element-non-indexed-header">Bizonyítás:</h4>    Képezzük e két maradékosztály szorzatát, azaz az [a]_n \odot [b]_n maradékosztályt. A \odot művelet <a href="https://youproof.hu/kriptografia/20-kongruencia-redukalt-maradekosztaly-euler-fuggveny-linearis-kongruencia-maradekrendszer-euler-fermat-tetel/#yp-element-5352" class="yp-element-link">20.5. Tétel</a>ben ismertetett definíciója alapján ez épp az [ab]_n maradékosztály lesz. Először azt kell bizonyítanunk, hogy ez a maradékosztály Fermat-tanú. Ez a <a href="https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/#yp-element-6264" class="yp-element-link">23.3. Definíció</a> alapján az alábbit jelenti:   (ab)^{n-1} \ \cancel{\equiv} \ 1 \pmod n   Az (ab)^{n-1} kifejezés a hatványozás azonosságairól szóló <a href="https://youproof.hu/kriptografia/18-modularis-aritmetika-homomorfizmus-kongruencia-reszgyuru-ideal-maradekosztalygyuru/#yp-element-4612" class="yp-element-link">18.8. Tétel</a> 1. pontja alapján így is írható: a^{n-1}b^{n-1}. Mivel b\neq 0 és [b]_n nem Fermat-tanú, ezért a <a href="https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/#yp-element-6264" class="yp-element-link">23.3. Definíció</a> alapján teljesül az alábbi kongruencia:   b^{n-1}\equiv 1\pmod n   Következésképp a <a href="https://youproof.hu/kriptografia/20-kongruencia-redukalt-maradekosztaly-euler-fuggveny-linearis-kongruencia-maradekrendszer-euler-fermat-tetel/#yp-element-5263" class="yp-element-link">20.2. Tétel</a> 5. pontja miatt teljesül az alábbi kongruencia is:   \underbrace{a^{n-1}b^{n-1}}_{=(ab)^{n-1}} \equiv a^{n-1} \pmod n   Mivel [a]_n Fermat-tanú, ezért ugyancsak a <a href="https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/#yp-element-6264" class="yp-element-link">23.3. Definíció</a> alapján a jobboldali kifejezés biztosan nem kongruens 1-gyel modulo n. Így hát a baloldali kifejezés sem, azaz:   (ab)^n \ \cancel{\equiv} \ 1\pmod n   Ez tehát azt jelenti, hogy az [ab]_n=[a]_n\odot [b]_n maradékosztály valóban egy Fermat-tanú.   Most azt igazoljuk, hogy [ab]_n egy redukált maradékosztály. Mivel az [a]_n egy redukált maradékosztály, ezért a egy redukált maradékrendszer egyik eleme. Továbbá, mivel [b]_n szintén egy redukált maradékosztály, ezért b relatív prím n-hez. Így tehát az ab szorzat a <a href="https://youproof.hu/kriptografia/20-kongruencia-redukalt-maradekosztaly-euler-fuggveny-linearis-kongruencia-maradekrendszer-euler-fermat-tetel/#yp-element-5498" class="yp-element-link">20.18. Tétel</a> miatt szintén egy redukált maradékrendszer egyik eleme lesz. Ebből következően az [ab]_n maradékosztály egy redukált maradékosztály.   ∎</div> A második segédtétel arra vonatkozóan mond ki egy fontos állítást, hogy mi történik akkor, ha egymástól különböző maradékosztályokat egyesével végigszorozzuk ugyanazzal a redukált maradékosztállyal.  <div class="yp-element-normal" id="yp-element-6283">  <h4 class="yp-element-indexed-header">23.5. Lemma:</h4>    Ha bármely két egymástól különböző [a]_n és [b]_n maradékosztályt megszorzunk egy tetszőleges [c]_n redukált maradékosztállyal, akkor az így kapott maradékosztályok is különböznek egymástól.   Azaz ha [a]_n \neq [b]_n, akkor [c]_n \odot [a]_n \neq [c]_n \odot [b]_n.   ♣</div>  <div class="yp-element-normal" id="yp-element-6284">  <h4 class="yp-element-non-indexed-header">Bizonyítás:</h4>    Tegyük fel indirekt, hogy nem ez a helyzet, vagyis annak ellenére, hogy [a]_n és [b]_n különböznek egymástól, mégiscsak teljesül az alábbi egyenlőség:   [c]_n \odot [a]_n = [c]_n \odot [b]_n   A \odot művelet <a href="https://youproof.hu/kriptografia/20-kongruencia-redukalt-maradekosztaly-euler-fuggveny-linearis-kongruencia-maradekrendszer-euler-fermat-tetel/#yp-element-5352" class="yp-element-link">20.5. Tétel</a>ben ismertetett definíciója alapján ez az alábbit jelenti:   [ca]_n = [cb]_n   Az egész számok maradékosztályainak <a href="https://youproof.hu/kriptografia/20-kongruencia-redukalt-maradekosztaly-euler-fuggveny-linearis-kongruencia-maradekrendszer-euler-fermat-tetel/#yp-element-5345" class="yp-element-link">20.4. Tétel</a>ben bevezetett definíciója alapján ugyanezt a kongruenciák nyelvén is kifejezhetjük:   ca\equiv cb\pmod n   Mivel [c]_n egy redukált maradékosztály, ezért a <a href="https://youproof.hu/kriptografia/20-kongruencia-redukalt-maradekosztaly-euler-fuggveny-linearis-kongruencia-maradekrendszer-euler-fermat-tetel/#yp-element-5482" class="yp-element-link">20.14. Tétel</a> alapján c relatív prím n-hez, és így a kongruencia a <a href="https://youproof.hu/kriptografia/20-kongruencia-redukalt-maradekosztaly-euler-fuggveny-linearis-kongruencia-maradekrendszer-euler-fermat-tetel/#yp-element-5333" class="yp-element-link">20.3. Tétel</a> utáni megjegyzés szerint minden további nélkül egyszerűsíthető c-vel. Ezt kapjuk tehát:   a\equiv b\pmod n   Ez viszont azt jelenti, hogy indirekt feltételezésünkkel ellentétben a és b mégiscsak ugyanazt a maradékosztályt reprezentálja, ami ellentmondás.   ∎</div> E két segédtétel segítségével mostmár könnyedén igazolhatjuk a Fermat-tanúk számára vonatkozó alsó becslésünket.  <div class="yp-element-normal" id="yp-element-6273">  <h4 class="yp-element-indexed-header">23.6. Tétel:</h4>    Legyen n\gt 1 egy tetszőleges pozitív egész szám. Amennyiben n-nek létezik Fermat-tanúja a redukált maradékosztályok között, akkor a modulo n redukált maradékosztályoknak legalább a fele Fermat-tanú.   ♣</div>  <div class="yp-element-normal" id="yp-element-6275">  <h4 class="yp-element-non-indexed-header">Bizonyítás:</h4>    Tegyük fel, hogy összesen k darab olyan modulo n redukált maradékosztály van, amely nem Fermat-tanú. Legyenek például ezek az alábbiak, amelyek tehát páronként különböző redukált maradékosztályok:   \begin{aligned}&[a_1]_n \\ &[a_2]_n \\ &[a_3]_n \\ &\vdots \\ &[a_k]_n \end{aligned}   Tegyük fel továbbá, hogy n-nek létezik legalább egy Fermat-tanúja a redukált maradékosztályok között. Legyen ez például az alábbi redukált maradékosztály:   [b]_n   Amennyiben ezzel a [b]_n Fermat-tanúval végigszorozzuk a fenti k darab nem Fermat-tanút, akkor az alábbi maradékosztályokat kapjuk, amelyek a <a href="https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/#yp-element-6279" class="yp-element-link">23.4. Lemma</a> alapján szintén mindannyian Fermat-tanúk és redukált maradékosztályok:   \begin{aligned}[b]_n &\odot [a_1]_n \\ [b]_n &\odot [a_2]_n \\ [b]_n &\odot [a_3]_n \\ &\vdots \\ [b]_n &\odot [a_k]_n \end{aligned}   Mivel a szorzáshoz használt [b]_n egy redukált maradékosztály, továbbá az [a_1]_n, [a_2]_n, ..., [a_k]_n redukált maradékosztályok páronként különbözőek voltak, emiatt a <a href="https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/#yp-element-6283" class="yp-element-link">23.5. Lemma</a> alapján az eredményül kapott szorzatok is páronként különböző redukált maradékosztályok. Ráadásul ezek az [a_1]_n, [a_2]_n, ..., [a_k]_n redukált maradékosztályoktól is biztosan különböznek, hiszen azok nem is voltak Fermat-tanúk.   Ha tehát teljesül a tétel feltétele, miszerint n-hez létezik legalább egy Fermat-tanú a redukált maradékosztályok között, akkor minden nem Fermat-tanúhoz elő tudunk állítani egy-egy újabb Fermat-tanút szintén a redukált maradékosztályok között. Más szavakkal a redukált maradékosztályok között minimum annyi Fermat-tanú van, mint ahány nem Fermat-tanú, ráadásul létezhetnek további Fermat-tanúk is. A modulo n redukált maradékosztályoknak tehát valóban legalább a fele Fermat-tanú.   ∎</div> Na és akkor mi van?! – kérdezhetné az Olvasó. Nos, az a helyzet, hogy ezt az első látásra nem túl érdekes tényt Alice és Bob egy meglehetősen pofátlan kis trükkel prímteszteléshez tudja felhasználni. Ezt az eljárást Fermat-prímtesztnek nevezzük, és a következőképpen néz ki: <ol><li>Az algoritmus bemenete egy n\gt 1 pozitív egész szám, amelyről el kellene dönteni, hogy prím-e vagy összetett.</li><li>Válasszunk véletlenszerűen egy tetszőleges 1 és n közötti a egész számot, azaz 1\lt a\lt n.</li><li>A <a href="https://youproof.hu/kriptografia/17-euklideszi-algoritmus-maradekos-osztas-legnagyobb-kozos-oszto-euklideszi-gyuru/#yp-element-4345" class="yp-element-link">17.17. Tétel</a> bizonyításában ismertetett euklidészi algoritmus segítségével számítsuk ki az (a,n) kitüntetett közös osztót. Ha (a,n)\neq 1, akkor az algoritmus leáll a következő válasszal: az n egész szám biztosan összetett, és az egyik osztója (a,n). Ha (a,n)=1, akkor folytassuk a 4. lépéstől.</li><li>A <a rel="noreferrer noopener" href="https://youproof.hu/kriptografia/21-rsa-algoritmus-kibovitett-euklideszi-algoritmus-euler-fuggveny-kulcsgeneralas-ismetelt-negyzetreemeles-modszere/" target="_blank">21. részben</a> ismertetett ismételt négyzetreemelések módszerével ellenőrizzük le, hogy teljesül-e az a^{n-1}\equiv 1\pmod n kongruencia. Amennyiben nem teljesül a kongruencia, akkor az algoritmus leáll a következő válasszal: az n egész szám biztosan összetett, de nem találtuk meg egyetlen osztóját sem. Amennyiben teljesül a kongruencia, akkor az algoritmus a következő válasszal áll le: az n egész szám „valószínűleg” prím.</li></ol> <h4 class="wp-block-heading">„Valószínűleg” prím?!</h4> Ez az egész elsőre teljesen értelmetlennek tűnik, ezért most vizsgáljuk meg, hogy miről is van szó tulajdonképpen. Képzeljük el, hogy a bemenő n egész szám valójában összetett, ám ezt szeretné minél jobban eltitkolni előlünk. Mi azonban a kis Fermat-tételből (<a href="https://youproof.hu/kriptografia/22-kinai-maradektetel-konguenciarendszerek-kis-fermat-tetel-rsa-bizonyitas-gyuruk-direkt-szorzata-rsa-dekodolas/#yp-element-5892" class="yp-element-link">22.1. Tétel</a>) tudjuk, hogy n esetleges összetettségét egy Fermat-tanú egyértelműen leleplezné. Ezért az összes nemnulla modulo n maradékosztályt szépen bedobáljuk egy képzeletbeli kalapba, majd becsukjuk a szemünket, és teljesen véletlenszerűen kihúzunk közülük egyet. Olyan ez, akárcsak egy lottósorsolás. Ez lenne tehát az algoritmus 2. lépése. A 3. lépésben azt vizsgáljuk meg, hogy egy redukált maradékosztályt húztunk-e ki. Annak, hogy nem, gyakorlatilag 0 az esélye, de ha mégis, akkor ez leleplezi n-et, ráadásul még egy osztóját is megkapjuk. Majdnem biztos azonban, hogy tovább kell mennünk a 4. lépésre. Ezen a ponton már tudjuk, hogy a kiválasztott maradékosztály egy redukált maradékosztály. Ebben a lépésben azt ellenőrizzük le, hogy véletlenül nem egy Fermat-tanút találtunk-e. Ha igen – azaz a vizsgált kongruencia nem teljesült – akkor n lelepleződött, hiszen a kis Fermat-tétel miatt biztosan összetett. Ha azonban nem Fermat-tanút fogtunk ki – azaz a vizsgált kongruencia teljesül –, akkor nem tudunk semmi biztosat mondani n-ről, ugyanis a kis Fermat-tétel megfordítása nem igaz. Azt viszont az előző szakaszban bizonyított <a href="https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/#yp-element-6273" class="yp-element-link">23.6. Tétel</a> alapján tudjuk, hogy a kalapban lévő redukált maradékosztályoknak legalább a fele – ám a tapasztalat alapján általában ennél jóval nagyobb része – Fermat-tanú. Így annak valószínűsége meglehetősen kicsi, hogy pont belehúztunk abba a néhány kósza nem Fermat-tanúba, miközben n összetett. Ennél sokkal valószínűbb, hogy n ténylegesen prím, és emiatt valóban nincs egyetlen Fermat-tanú sem abban a bizonyos kalapban. Ám biztosat ezen a ponton nem tudunk mondani, és ez az oka ennek a meglehetősen furcsán hangzó „valószínűleg prím” válasznak. A Fermat-tanúk számára vonatkozó, a <a href="https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/#yp-element-6273" class="yp-element-link">23.6. Tétel</a>ben bizonyított alsó becslés ugyan önmagában nem túl erős, azonban Alice és Bob megteheti, hogy többször is húz a kalapból. A Fermat-tanúság ellenőrzése ugyanis – mint említettük – az ismételt négyzetreemelések módszerével rendkívül gyorsan elvégezhető. Tegyük fel, hogy a lehető legrosszabb a helyzet, és a redukált maradékosztályoknak mindössze csak a fele Fermat-tanú. Ekkor 50% annak valószínűsége, hogy főhőseink egy véletlenszerű választással pont a másik feléből választanak egy redukált maradékosztályt. Annak pedig már csak 25%, hogy ez kétszer egymás után is megtörténik. Az, hogy egy újabb, harmadik húzással sem találunk Fermat-tanút, már csak 12.5% valószínűséggel következik be. És így tovább, minden újabb húzással megfeleződik annak valószínűsége, hogy tévesen prímszámmá nyilvánítjuk n-et. Tegyük fel például, hogy 100 teljesen véletlenszerűen kiválasztott redukált maradékosztály egyike sem bizonyul Fermat-tanúnak. Ennek már csupán annyi az esélye, mint 100-szor zsinórban eltalálni, hogy egy feldobott pénzérme fej vagy írás lesz-e. Ez nagyságrendileg kevésbé valószínű, mint hogy valakinek 3-szor egymás után telitalálata lesz az 5-ös lottón. Van azonban egy kis probléma ezzel a prímteszttel: sajnos léteznek olyan összetett számok, amelyeket nem lehet ilyen módon kiszűrni. <h4 class="wp-block-heading">Univerzális álprímek</h4> Térjünk vissza egy kicsit az előző szakasz elején szereplő táblázathoz. Itt a második oszlop a modulo n redukált maradékosztályok számát mutatja – ezt \varphi(n)-nel jelöltük –, a harmadik pedig azt, hogy ezek közül hány olyan van, amely NEM Fermat-tanú – ezt pedig l(n)-nel jelöltük. Értelemszerűen a prímszámok esetén ez a két érték megegyezik, hiszen egy prímszámhoz nyilván nem létezik az összetettségét igazoló Fermat-tanú. Kérdés, hogy vajon létezik-e olyan összetett szám, amelyhez szintén nincs Fermat-tanú a redukált maradékosztályok között. A táblázatban felhívtuk a figyelmet az 561 egész számra, amely épp ezzel a szemtelen tulajdonsággal rendelkezik. Ezeknek a számoknak külön nevük is van.  <div class="yp-element-normal" id="yp-element-6315">  <h4 class="yp-element-indexed-header">23.7. Definíció (Univerzális álprímek, Carmichael-számok):</h4>    Legyen n\gt 1 tetszőleges pozitív, továbbá a egy n-hez relatív prím egész szám, és tegyük fel, hogy n összetett. Amennyiben az [a]_n redukált maradékosztály NEM Fermat-tanú, akkor azt mondjuk, hogy n álprím az a alapra nézve.   Amennyiben a modulo n redukált maradékosztályok között egyáltalán nem létezik Fermat-tanú, akkor n-et univerzális álprímnek vagy Carmichael-számnak nevezzük.   ♣</div> Ha tehát véletlenül épp egy Carmichael-számba botlunk, akkor a Fermat-prímteszt azt nagyon nagy valószínűséggel tévesen prímnek fogja minősíteni, hiszen akárhány redukált maradékosztályt is húzunk ki a kalapból, azokra mind teljesülni fog a Fermat-kongruencia. Az ilyen számok összetettségét egyedül akkor fogjuk tudni detektálni, ha sikerül épp egy nem redukált maradékosztályt kisorsolni a kalapból. Ilyenkor ugyanis a 3. lépésben végrehajtott euklidészi algoritmus 1-től különböző eredménye lebuktatja a számunkat. Erre azonban gyakorlatilag semmi esély nincs, hiszen egy nagy szám esetén a maradékosztályoknak általában csak elenyésző hányada nem redukált maradékosztály. A figyelmes Olvasó észreveheti az említett táblázatból, hogy egy n univerzális álprímet mindössze az különbözteti meg egy valódi prímtől, hogy összetettsége miatt a [0]_n maradékosztályon kívül vannak még egyéb nem redukált maradékosztályok is. Ez onnan látszik, hogy a táblázat második oszlopában nem \varphi(n)=n-1 fog szerepelni, ahogyan a prímek esetében a <a href="https://youproof.hu/kriptografia/21-rsa-algoritmus-kibovitett-euklideszi-algoritmus-euler-fuggveny-kulcsgeneralas-ismetelt-negyzetreemeles-modszere/#yp-element-5700" class="yp-element-link">21.5. Tétel</a> alapján elvárható, hanem egy ennél kisebb szám. Ez valóban lebuktatja álprímünket. A gond csak az, hogy – mint ahogyan a <a rel="noreferrer noopener" href="https://youproof.hu/kriptografia/21-rsa-algoritmus-kibovitett-euklideszi-algoritmus-euler-fuggveny-kulcsgeneralas-ismetelt-negyzetreemeles-modszere#euler-function" target="_blank">21. részben</a> már említettük – az Euler-féle \varphi-függvény kiszámítására csak n prímtényezőinek ismeretében van esélyünk, máskülönben az idők végezetéig is eltarthat. Így erre nem tudunk támaszkodni. Érdekes kérdés, hogy vajon hány Carmichael-szám létezik? Ha esetleg ezek száma véges, akkor ezeket nyilvántarthatnánk a számítógép memóriájában, az algoritmus pedig leellenőrizhetné, hogy n véletlenül nem szerepel-e ebben a listában. Régóta ismeretes, hogy tetszőleges a\gt 1 egész szám esetén végtelen sok a alapú álprím létezik, az azonban sokáig nyitott kérdés volt, hogy vajon az univerzális álprímek száma is végtelen-e. Sajnálatos módon 1992-ben ezt is sikerült igazolni. Emiatt nem mehetünk el szó nélkül a probléma mellett, és az a^{n-1}\equiv 1\pmod n kongruencia ellenőrzésén kívül egyéb dolgokat is meg kell vizsgálnunk annak érdekében, hogy a Carmichael-számokat is ki tudjuk szűrni. <div id="miller-rabin-primality-test"></div> <h4 class="wp-block-heading">A Miller-Rabin prímteszt</h4> Ebben a szakaszban a Fermat-prímtesztünket fogjuk egy kicsit feljavítani annak érdekében, hogy a Carmichael-számokat is ki tudjuk szűrni. Előszöris szögezzük le, hogy a továbbiakban csak a páratlan n-ekkel fogunk foglalkozni. Ez nem jelent tényleges megszorítást, hiszen az utolsó számjegyből azonnal látszik, hogy páratlan vagy páros-e a bemenetünk. Ez utóbbi esetben nyilván megállhatunk, és összetettnek nyilváníthatjuk a számunkat, hiszen az osztható 2-vel. Az általánosság megsértése nélkül feltételezhetjük tehát, hogy n\gt 1 egy páratlan egész szám. Ekkor azonban az a^{n-1}\equiv 1\pmod n Fermat-kongruenciában szereplő n-1 kitevő biztosan páros lesz. Vagyis létezik olyan k_1 egész szám, amelyre teljesül az alábbi – és ezt meg is kapjuk, ha n-1-et „elosztjuk” 2-vel: n-1 = 2\cdot k_1 Ezután k_1-re vizsgáljuk meg, hogy páratlan-e vagy páros. Utóbbi esetben hasonlóképpen tovább bonthatjuk n-1-et, azaz létezni fog olyan k_2 egész szám, amelyre teljesül az alábbi: n-1 = 2\cdot 2\cdot k_2 És így tovább mindaddig bontjuk tovább a jobboldali tényezőt, amíg páratlan számot nem kapunk. Ez garantáltan be fog következni véges számú lépés után, máskülönben n-1 prímtényezős felbontásában végtelen sok 2-es tényező szerepelne, ami lehetetlen. Tegyük fel, hogy e darab lépés után egy valamilyen k páratlan számot kapunk. Ekkor n-1-re az alábbi kifejezést kaptuk: n-1=\underbrace{2\cdot 2\cdot \ldots \cdot 2}_{e \text{ darab}}\cdot k=2^e\cdot k Például ha az n=561 Carmichael-szám a bemenetünk, akkor n-1=560-ra az iménti felbontás után e=4 és k=35 adódik, hiszen: \begin{aligned}n-1=560&=2\cdot 280=\\&=2^2\cdot 140=\\&=2^3\cdot 70=\\&=2^4\cdot 35\end{aligned} Ilymódon kiszámítva az e és k értékét, a Fermat-tesztben használt a^{n-1}\equiv 1\pmod n kongruencia az alábbi alakot ölti: a^{2^e\cdot k}\equiv 1\pmod n Amennyiben tehát [a]_n egy redukált maradékosztály és n prím, akkor teljesül a fenti kongruencia. Ez viszont a <a href="https://youproof.hu/kriptografia/20-kongruencia-redukalt-maradekosztaly-euler-fuggveny-linearis-kongruencia-maradekrendszer-euler-fermat-tetel/#yp-element-5254" class="yp-element-link">20.1. Tétel</a> 3. pontja alapján azt jelenti, hogy n osztója az alábbi kifejezésnek: a^{2^e\cdot k}-1 Most ezt a kifejezést fogjuk szorzattá alakítani a következő tétel segítségével.  <div class="yp-element-normal" id="yp-element-6335">  <h4 class="yp-element-indexed-header">23.8. Tétel:</h4>    Legyenek adottak valamilyen tetszőleges e\geq 1 és k\geq 1 egész számok. Ekkor bármilyen a egész szám esetén teljesül az alábbi összefüggés:   a^{2^e\cdot k}-1 = (a^k-1)\cdot (a^k+1)\cdot (a^{2k}+1)\cdot (a^{4k}+1)\cdot \ldots \cdot (a^{2^{e-1}k}+1)     ♣</div>  <div class="yp-element-normal" id="yp-element-6338">  <h4 class="yp-element-non-indexed-header">Bizonyítás:</h4>    Azt a jól ismert azonosságot fogjuk használni, miszerint bármilyen kommutatív gyűrű tetszőleges x és y elemeire teljesül az alábbi:   x^2-y^2=(x-y)\cdot (x+y)   Ez a <a href="https://youproof.hu/kriptografia/14-egesz-szam-szorzas-absztrakt-algebra-neutralis-elem-inverz-kivonas-gyuru-ferdetest-test/#yp-element-3471" class="yp-element-link">14.12. Definíció</a>ben szereplő gyűrűaxiómák közvetlen következménye, amelyet most le is ellenőrzünk. Rögtön alkalmazhatjuk az 5. pontban lévő első disztributivitási szabályt:   (x-y)\cdot (x+y)=(x-y)\cdot x + (x-y)\cdot y=\ldots   A kapott összeg két tagjára a második disztributivitási szabályt alkalmazhatjuk. Figyelembe véve a <a href="https://youproof.hu/kriptografia/15-rendezett-gyuru-absztrakt-algebra-egesz-szam-rendezesi-relacio-rendezesi-axiomak/#yp-element-3576" class="yp-element-link">15.1. Tétel</a> 3. pontját valóban a fent szereplő kifejezést kapjuk:   \ldots = x^2-yx + xy-y^2 = x^2-y^2   Ezek után alkalmazhatjuk ezt az azonosságot az a^{2^ek}-1 kifejezésre. Ez ugyanis a hatványozás azonosságairól szóló <a href="https://youproof.hu/kriptografia/18-modularis-aritmetika-homomorfizmus-kongruencia-reszgyuru-ideal-maradekosztalygyuru/#yp-element-4612" class="yp-element-link">18.8. Tétel</a> 2. és 3. pontjai alapján a következőképpen alakítható át:   a^{2^ek}-1=a^{2^{e-1}\cdot k\cdot 2}-1=(a^{2^{e-1}\cdot k})^2-1   Erre már alkalmazhatjuk a fenti azonosságot x=a^{2^{e-1}\cdot k} és y=1 szereposztással:   (\underbrace{a^{2^{e-1}\cdot k}}_{=x})^2-(\underbrace{1}_{=y})^2=(\underbrace{a^{2^{e-1}\cdot k}}_{=x}-\underbrace{1}_{=y})\cdot (\underbrace{a^{2^{e-1}\cdot k}}_{=x}+\underbrace{1}_{=y})=\ldots   Amennyiben az e-1 kitevő még mindig nagyobb 0-nál, akkor a kapott szorzat első tényezőjére megismételhetjük a fenti eljárást:   \ldots=\underbrace{(a^{2^{e-2}\cdot k}-1)\cdot (a^{2^{e-2}\cdot k}+1)}_{=a^{2^{e-1}\cdot k}-1}\cdot (a^{2^{e-1}\cdot k}+1)=\ldots   Ha még az e-2 kitevő is nagyobb 0-nál, akkor az első tényezőt ugyanígy tovább bonthatjuk. Minden lépésben tovább fog csökkenni a kitevő, és előbb-utóbb – egészen pontosan e lépés után – eléri a 0-t. Ekkor épp a tételben szereplő szorzatot fogjuk kapni.   ∎</div> Tegyük fel például, hogy továbbra is az n=561 Carmichael-szám a bemenetünk. Az n-1=560-ból ugye már korábban kiszámítottuk az e=4 és k=35 értékeket. Ekkor az a^{n-1}-1=a^{560}-1 kifejezés az iménti tétel alapján így alakítható szorzattá: a^{560}-1=(a^{35}-1)\cdot (a^{35}+1)\cdot (a^{70}+1)\cdot (a^{140}+1)\cdot (a^{280}+1) Ha tehát [a]_{561} egy tetszőleges redukált maradékosztály, és az n=561 egy prímszám lenne, akkor ő garantáltan osztója lenne a baloldali a^{560}-1 kifejezésnek. Természetesen ez az oszthatóság teljesülhet egészen más okból is, és – minthogy az n=561 egy Carmichael-szám – jelen esetben teljesül is bármilyen [a]_{561} redukált maradékosztályra. A Fermat-prímteszt ezen a ponton annak rendje és módja szerint meg is bukik, hiszen néhány véletlenszerűen kiválasztott [a]_{561} redukált maradékosztály vizsgálata után tévesen arra a következtetésre jut, hogy az n=561 „valószínűleg prím”. Ezen a ponton a Miller-Rabin-prímteszt továbbmegy, és az n=561 esetleges prímtulajdonságát (<a href="https://youproof.hu/kriptografia/16-oszhatosag-egyseg-asszocialt-felbonthatatlan-prim-szamelmelet-alaptetele/#yp-element-4064" class="yp-element-link">16.13. Definíció</a>) próbálja meg cáfolni a kiválasztott [a]_{561} redukált maradékosztály segítségével. Ha ugyanis n=561 osztója a baloldali a^{560}-1 egész számnak, akkor a prímtulajdonság miatt a <a href="https://youproof.hu/kriptografia/16-oszhatosag-egyseg-asszocialt-felbonthatatlan-prim-szamelmelet-alaptetele/#yp-element-4064" class="yp-element-link">16.13. Definíció</a> utáni megjegyzés alapján osztója kell legyen legalább az egyik jobboldalon szereplő tényezőnek is. Azaz teljesülnie kell az alábbi oszthatóságok közül legalább egynek tetszőleges [a]_{561} redukált maradékosztály esetén: \begin{aligned}561&|a^{35}-1 \\ 561&|a^{35}+1 \\ 561&|a^{70}+1 \\ 561&|a^{140}+1 \\ 561&|a^{280}+1\end{aligned} Ez viszont a <a href="https://youproof.hu/kriptografia/20-kongruencia-redukalt-maradekosztaly-euler-fuggveny-linearis-kongruencia-maradekrendszer-euler-fermat-tetel/#yp-element-5254" class="yp-element-link">20.1. Tétel</a> 3. pontja alapján azt jelenti, hogy teljesülnie kell legalább az egyik alábbi kongruenciának tetszőleges [a]_{561} redukált maradékosztály esetén: \begin{aligned}a^{35}&\equiv +1\pmod{561} \\ a^{35}&\equiv -1\pmod{561} \\ a^{70}&\equiv -1\pmod{561} \\ a^{140}&\equiv -1\pmod{561} \\ a^{280}&\equiv -1\pmod{561} \end{aligned} Más megfogalmazásban ez azt jelenti, hogy amennyiben találunk egy olyan [a]_{561} redukált maradékosztályt, amely esetén a fenti kongruenciák közül egyik sem teljesül, akkor az n=561 biztosan nem lehet prím. Egy ilyen maradékosztály tehát „leleplezi” vagy „tanúsítja” az n=561 összetettségét. Vizsgáljuk meg például a [2]_{561} redukált maradékosztályt, azaz legyen a=2. Az <a rel="noreferrer noopener" href="https://www.mtholyoke.edu/courses/quenell/s2003/ma139/js/powermod.html" target="_blank">itt</a> lévő kalkulátor segítségével leellenőrizhetjük a fenti kongruenciákat: \begin{aligned}2^{35} \equiv 263 \ &\cancel{\equiv}\ +1\pmod{561} \\ 2^{35} \equiv 263 \ &\cancel{\equiv}\ -1\pmod{561} \\ 2^{70}\equiv 166 \ &\cancel{\equiv}\ -1\pmod{561} \\ 2^{140}\equiv 67 \ &\cancel{\equiv}\ -1\pmod{561} \\ 2^{280}\equiv 1 \ &\cancel{\equiv}\ -1\pmod{561} \end{aligned} Minthogy egyetlen kongruencia sem teljesül, ezért az eddigi okfejtés alapján az n=561 Carmichael-szám biztosan összetett, azaz megbukott a Miller-Rabin-prímteszten. Az eljárás általános megfogalmazásához most bevezetünk egy új tanú fogalmat.  <div class="yp-element-normal" id="yp-element-6359">  <h4 class="yp-element-indexed-header">23.9. Definíció (Miller-Rabin-tanú):</h4>    Legyen n\gt 1 egy tetszőleges páratlan szám, a pedig tetszőleges egész szám, amely nem többszöröse n-nek, azaz n\nmid a. Képezzük azt az e\geq 1 kitevőt és k\geq 1 páratlan számot, amelyekre teljesül az alábbi:   n-1=2^e\cdot k   Tegyük fel továbbá, hogy az alábbi kongruenciák egyike sem teljesül:   \begin{aligned}a^k&\equiv +1\pmod n \\ a^k&\equiv -1\pmod n \\ a^{2k}&\equiv -1\pmod n \\ a^{4k}&\equiv -1\pmod n \\ &\vdots \\ a^{2^{e-1}\cdot k}&\equiv -1\pmod n\end{aligned}   Ekkor az a egész szám által reprezentált [a]_n maradékosztályt az n egész szám Miller-Rabin-tanújának nevezzük.   ♣</div>  <div class="yp-element-normal" id="yp-element-6361">  <h4 class="yp-element-non-indexed-header">Megjegyzés:</h4>    A Fermat-tanú <a href="https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/#yp-element-6264" class="yp-element-link">23.3. Definíció</a>jához hasonlóan itt is teljes maradékosztályokra célszerű vonatkoztatni ezt a fogalmat. Ha ugyanis egy b egész szám a-val azonos modulo n maradékosztályban van, akkor teljesül az a\equiv b\pmod n kongruencia, és így a <a href="https://youproof.hu/kriptografia/20-kongruencia-redukalt-maradekosztaly-euler-fuggveny-linearis-kongruencia-maradekrendszer-euler-fermat-tetel/#yp-element-5263" class="yp-element-link">20.2. Tétel</a> 8. pontja alapján teljesülnek az alábbi kongruenciák is:   \begin{aligned}a^k&\equiv b^k\pmod n \\ a^{2k}&\equiv b^{2k}\pmod n \\ a^{4k}&\equiv b^{4k}\pmod n \\ &\vdots \\ a^{2^{e-1}\cdot k}&\equiv b^{2^{e-1}\cdot k}\pmod n\end{aligned}   Mármost ha a baloldal nem kongruens a definícióban szereplő számokkal, akkor a jobboldal sem. Így tehát az [a]_n maradékosztálynak vagy minden eleme teljesíti a Miller-Rabin-tanúkkal szemben támasztott kritériumokat, vagy egyik sem.   Szintén a Fermat-tanú <a href="https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/#yp-element-6264" class="yp-element-link">23.3. Definíció</a>jához hasonlóan itt sem kell kikötni, hogy [a]_n egy redukált maradékosztály, hiszen ha van egységtől különböző közös osztója a-nak és n-nek, akkor n nyilván összetett. Nem mellesleg itt is megjegyezzük, hogy a Miller-Rabin-kongruenciák amúgysem teljesülhetnének, amennyiben [a]_n nem egy redukált maradékosztály, azaz (a,n) nem egység. Ennek indoklása szinte szóról szóra megegyezik a <a href="https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/#yp-element-6264" class="yp-element-link">23.3. Definíció</a> utáni megjegyzésben leírtakkal.   Ez tehát azt jelenti, hogy NEM Miller-Rabin-tanú csak redukált maradékosztály lehet. Ezen túlmenően a <a href="https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/#yp-element-6335" class="yp-element-link">23.8. Tétel</a> miatt ha egy [a]_n redukált maradékosztály NEM Miller-Rabin tanú – azaz teljesül a definícióban szereplő kongruenciák közül legalább az egyik –, akkor Fermat-tanú SEM lehet. Ha ugyanis teljesül legalább az egyik kongruencia, akkor a <a href="https://youproof.hu/kriptografia/20-kongruencia-redukalt-maradekosztaly-euler-fuggveny-linearis-kongruencia-maradekrendszer-euler-fermat-tetel/#yp-element-5254" class="yp-element-link">20.1. Tétel</a> 3. pontja alapján n osztója az alábbi kifejezések közül legalább az egyiknek:   \begin{aligned}&a^k-1 \\ &a^k+1 \\ &a^{2k}+1 \\ &a^{4k}+1 \\ &\vdots \\ &a^{2^{e-1}\cdot k}+1\end{aligned}   Ám e kifejezések szorzata a <a href="https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/#yp-element-6335" class="yp-element-link">23.8. Tétel</a> alapján épp a^{n-1}-1, aminek n a <a href="https://youproof.hu/kriptografia/16-oszhatosag-egyseg-asszocialt-felbonthatatlan-prim-szamelmelet-alaptetele/#yp-element-3894" class="yp-element-link">16.2. Tétel</a> 7. pontja miatt szintén osztója. Azaz teljesül az a^{n-1}\equiv 1\pmod n kongruencia, és így az [a]_n redukált maradékosztály valóban nem Fermat-tanú. Másként fogalmazva ez azt jelenti, hogy minden Fermat-tanú egyúttal Miller-Rabin-tanú is, vagyis az új definíció tágítani igyekszik a lehetséges tanúk körét.   Az alábbi ábrán a NEM Miller-Rabin-tanúk és a NEM Fermat-tanúk elhelyezkedése látható a modulo n maradékosztályok között.   <div class="wp-block-image"><figure class="aligncenter size-large"><img loading="lazy" decoding="async" width="300" height="255" src="https://youproof.hu/wp-content/uploads/kriptografia_23_nem_miller_rabin_tanuk_elhelyezkedese.jpg" alt="A nem Miller-Rabin-tanúk elhelyezkedése" class="wp-image-6471"/><figcaption>A nem Miller-Rabin-tanúk elhelyezkedése</figcaption></figure></div>   ♣</div> Felmerül a kérdés, hogy vajon a tanúk körének tágítását nem vittük-e túlzásba. Azaz nem lehetséges-e, hogy ha Fermat-tanúja nem is, de Miller-Rabin-tanúja már lehet esetleg prímszámoknak is. Az alábbi tétel szerint szerencsére nem ez a helyzet.  <div class="yp-element-normal" id="yp-element-6365">  <h4 class="yp-element-indexed-header">23.10. Tétel:</h4>    Semmilyen 1-nél nagyobb páratlan prímszámnak nincs Miller-Rabin-tanúja. Másként fogalmazva ha egy 1-nél nagyobb n páratlan számnak van Miller-Rabin-tanúja, akkor n összetett.   ♣</div>  <div class="yp-element-normal" id="yp-element-6367">  <h4 class="yp-element-non-indexed-header">Bizonyítás:</h4>    Legyen n\gt 1 egy tetszőleges páratlan prímszám, továbbá legyen adva egy tetszőleges [a]_n redukált maradékosztály. Képezzük azt az e\geq 1 kitevőt és k\geq 1 páratlan számot, amelyekre teljesülnek az alábbiak:   n-1=2^e\cdot k   Azt kell igazolni, hogy [a]_n nem lehet Miller-Rabin-tanú, azaz az alábbi kongruenciák közül legalább az egyiknek teljesülnie kell:   \begin{aligned}a^k&\equiv +1\pmod n \\ a^k&\equiv -1 \\ a^{2k}&\equiv -1\pmod n \\ a^{4k}&\equiv -1\pmod n \\ &\vdots \\ a^{2^{e-1}\cdot k}&\equiv -1\pmod n\end{aligned}   Mivel n prím, továbbá (a,n)=1 – hiszen [a]_n egy redukált maradékosztály –, ezért a kis Fermat-tétel (<a href="https://youproof.hu/kriptografia/22-kinai-maradektetel-konguenciarendszerek-kis-fermat-tetel-rsa-bizonyitas-gyuruk-direkt-szorzata-rsa-dekodolas/#yp-element-5892" class="yp-element-link">22.1. Tétel</a>) miatt teljesül rá az alábbi kongruencia:   a^{\overbrace{2^e\cdot k}^{=n-1}}\equiv 1\pmod n   Ez a <a href="https://youproof.hu/kriptografia/20-kongruencia-redukalt-maradekosztaly-euler-fuggveny-linearis-kongruencia-maradekrendszer-euler-fermat-tetel/#yp-element-5254" class="yp-element-link">20.1. Tétel</a> 3. pontja alapján azt jelenti, hogy teljesül az alábbi oszthatóság:   n|a^{2^e\cdot k}-1   Az oszthatóságban szereplő jobboldali kifejezést a <a href="https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/#yp-element-6335" class="yp-element-link">23.8. Tétel</a> alapján szorzatba fejthetjük:   n|(a^k-1)\cdot (a^k+1)\cdot (a^{2k}+1)\cdot (a^{4k}+1)\cdot \ldots \cdot (a^{2^{e-1}k}+1)   Mivel n prím, ezért a <a href="https://youproof.hu/kriptografia/16-oszhatosag-egyseg-asszocialt-felbonthatatlan-prim-szamelmelet-alaptetele/#yp-element-4064" class="yp-element-link">16.13. Definíció</a> utáni megjegyzés szerint legalább az egyik jobboldali tényezőnek osztója kell legyen. Azaz az alábbi oszthatóságok közül legalább az egyiknek teljesülnie kell:   \begin{aligned}n&|a^k-1 \\ n&|a^k+1 \\ n&|a^{2k}+1 \\ n&|a^{4k}+1 \\ &\vdots \\ n&|a^{2^{e-1}k}+1 \end{aligned}   A <a href="https://youproof.hu/kriptografia/20-kongruencia-redukalt-maradekosztaly-euler-fuggveny-linearis-kongruencia-maradekrendszer-euler-fermat-tetel/#yp-element-5254" class="yp-element-link">20.1. Tétel</a> 3. pontja alapján ez tehát azt jelenti, hogy legalább az egyik kongruenciának teljesülnie kell az alábbiak közül:   \begin{aligned}a^k\equiv +1\pmod n \\ a^k\equiv -1\pmod n \\ a^{2k}\equiv -1\pmod n \\ a^{4k}\equiv -1\pmod n \\ &\vdots \\ a^{2^{e-1}k}\equiv -1\pmod n \end{aligned}   Ez viszont a <a href="https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/#yp-element-6359" class="yp-element-link">23.9. Definíció</a> szerint épp azt jelenti, hogy az [a]_n maradékosztály nem Miller-Rabin-tanú.   ∎</div> Ezekután ismertetjük a Miller-Rabin-prímtesztelő eljárást, amely tehát a Fermat-prímtesztnek a továbbfejlesztett változata: <ol><li>Az algoritmus bemenete egy n\gt 1 páratlan egész szám, amelyről el kellene dönteni, hogy prím-e vagy összetett.</li><li>Válasszunk véletlenszerűen egy tetszőleges 1 és n közötti a egész számot, azaz 1\lt a\lt n.</li><li>A <a href="https://youproof.hu/kriptografia/17-euklideszi-algoritmus-maradekos-osztas-legnagyobb-kozos-oszto-euklideszi-gyuru/#yp-element-4345" class="yp-element-link">17.17. Tétel</a> bizonyításában ismertetett euklidészi algoritmus segítségével számítsuk ki az (a,n) kitüntetett közös osztót. Ha (a,n)\neq 1, akkor az algoritmus leáll a következő válasszal: az n egész szám biztosan összetett, és az egyik osztója (a,n). Ha (a,n)=1, akkor folytassuk a 4. lépéstől.</li><li>Képezzük azt az e\geq 1 kitevőt és k\geq 1 páratlan számot, amelyre n-1=2^e\cdot k teljesül.</li><li>A <a rel="noreferrer noopener" href="https://youproof.hu/kriptografia/21-rsa-algoritmus-kibovitett-euklideszi-algoritmus-euler-fuggveny-kulcsgeneralas-ismetelt-negyzetreemeles-modszere/" target="_blank">21. részben</a> ismertetett ismételt négyzetreemelések módszerével ellenőrizzük le, hogy az [a]_n maradékosztályra teljesül-e legalább az egyik a <a href="https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/#yp-element-6359" class="yp-element-link">23.9. Definíció</a>ban felsorolt kongruenciák közül. Amennyiben nem teljesül egyetlen kongruencia sem, akkor Miller-Rabin-tanút találtunk, és az algoritmus leáll a következő válasszal: az n egész szám biztosan összetett, de nem találtuk meg egyetlen osztóját sem. Amennyiben teljesül legalább az egyik kongruencia, akkor az algoritmus a következő válasszal áll le: az n egész szám „valószínűleg” prím.</li></ol> Már megint csak „valószínűleg” prím? – kérdezhetné teljes joggal az Olvasó. Látszólag valóban nem kerültünk közelebb a prímek azonosításához, hiszen ismét csak összetett számokat tudunk egyértelműen leleplezni. Ha azonban szerencsétlenül épp egy olyan maradékosztályt sikerült kihúzni a kalapból, amely nem Miller-Rabin-tanú, akkor ismét csak annyit mondhatunk, hogy a kérdéses szám „valószínűleg” prím. Ez valóban így van, azonban a Fermat-prímteszthez hasonlóan itt is megtehetjük, hogy többször húzunk a kalapból. Ezen túlmenően a Miller-Rabin-tanú <a href="https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/#yp-element-6359" class="yp-element-link">23.9. Definíció</a>ja utáni megjegyzés alapján egy adott n-hez tartozó Miller-Rabin-tanúk köre biztosan nem szűkebb, mint az ugyanezen n-hez tartozó Fermat-tanúk köre. Sőt, azt is láthattuk, hogy az n=561-nek egyáltalán nincs Fermat-tanúja – hiszen Carmichael-számról van szó. Ezzel szemben például a [2]_{561} maradékosztály „lebuktatja” ezt a számot is, hiszen ő egy Miller-Rabin-tanú, amely bizonyítja az 561 összetettségét. Úgy tűnik tehát, mintha a Miller-Rabin-prímteszt elől még a Carmichael-számok sem tudnának „elbújni”, ami kétségkívül hatalmas előrelépés. De vajon tényleg nem léteznek univerzális álprímek erre a tesztre nézve? Sajnos ahhoz, hogy ezt megválaszolhassuk, az absztrakt algebra egy rendkívül fontos ágának, nevezetesen az úgynevezett csoportelméletnek az eszköztárára lesz szükségünk. Így ezt csak a következő részben tudjuk majd igazolni. Most azonban térjünk vissza egy kicsit az RSA-kulcsgenerálás kérdésköréhez. Nem árt ugyanis, ha felhívjuk Alice és Bob figyelmét néhány fontos dologra, amire vigyázniuk kell, ha nem akarják, hogy Eve és Mallory borsot törjön az orruk alá. <h4 class="wp-block-heading">A Fermat-faktorizáció</h4> Az RSA implementációja során sok apró részleten múlhat a biztonság. Számos hatékony támadás ismert ugyanis, amelyek az üzenethalmaz, a kulcsgeneráláshoz használt prímpár, valamint a kódoló és dekódoló kulcs nem elég körültekintő megválasztását használják ki. Ezt néhány példán keresztül illusztráljuk, amelyek közül az első az úgynevezett Fermat-faktorizációs algoritmus. Ez az eljárás bizonyos körülmények között lehetővé teszi egy támadó számára, hogy hatékonyan kiszámíthassa a kódoláshoz és dekódoláshoz használt n modulus prímtényezőit, és így tulajdonképpen ő maga is a titkos kulcs birtokába juthasson. Erre akkor nyílik lehetősége, ha a prímtényezők közötti különbség nem eléggé nagy. Ebben az esetben a két prímtényező közel van a <a href="https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/#yp-element-6234" class="yp-element-link">23.2. Tétel</a>ben szereplő r számhoz. Ez ugye a legnagyobb olyan egész szám, amelynek négyzete még éppen nemnagyobb n-nél. Így ennek a környékén jó eséllyel hamar megtalálhatjuk a prímtényezőket. Az erre szolgáló alább ismertetett módszer magától <a rel="noreferrer noopener" href="https://hu.wikipedia.org/wiki/Pierre_de_Fermat" target="_blank">Pierre de Fermat</a>-tól származik, amely a <a href="https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/#yp-element-6335" class="yp-element-link">23.8. Tétel</a> bizonyításának elején már említett x^2-y^2 = (x+y)\cdot (x-y) összefüggésen alapul. Képzeljük magunkat Eve helyébe, és tegyük fel, hogy az n=57\ 319\ 249\ 499 RSA-modulus prímtényezőit szeretnénk megtalálni. Azaz keressük azt a p és q prímszámot, amelyre teljesül az alábbi egyenlet – itt nyugodtan feltételezhetjük, hogy p\gt q, ha pedig mégsem, akkor nevezzük el őket fordítva: n=p\cdot q Ez első látásra reménytelennek tűnik, azonban abban reménykedhetünk, hogy az ismeretlen p és q prímtényezőket a kulcsgeneráláskor óvatlanul választották ki, és a különbségük kicsi. Most megmutatjuk, hogy mindig léteznek olyan a és b egész számok, amelyeknek összege p-vel, különbsége pedig q-val egyenlő. Azaz: \begin{aligned}p&=a+b \\ q&=a-b\end{aligned} Adjuk össze, és vonjuk ki egymásból a két egyenletet: \begin{aligned}p+q&=2a \\ p-q&=2b\end{aligned} Mivel p és q is biztosan páratlan – hiszen mindketten 2-től különböző prímek – ezért a fenti két egyenlet baloldalán álló p+q összeg és p-q különbség biztosan páros, azaz osztható 2-vel. A keresett a és b egész számok tehát valóban léteznek. Ekkor a fentebb említett összefüggés alapján: n=(\underbrace{a+b}_{=p})\cdot (\underbrace{a-b}_{=q})=a^2-b^2 Ha valóban igaz a feltételezésünk, miszerint a két prím egymáshoz közel van, akkor a p-q=2b összefüggés alapján b kicsi. Ha viszont b kicsi, akkor a négyzete is kicsi, amit az n=a^2-b^2 összefüggés jobboldaláról elhanyagolhatunk. Azaz feltételezhetjük, hogy a keresett a közel lesz a <a href="https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/#yp-element-6234" class="yp-element-link">23.2. Tétel</a>ben szereplő r számhoz, ami ugye a legnagyobb olyan egész szám, amelynek a négyzete nemnagyobb n-nél. Ha most az n=a^2-b^2 összefüggésből kifejezzük b^2-et, akkor az alábbit kapjuk: b^2=a^2-n Feladatunk a megkeresése. Azt tudjuk, hogy r környékén van, ezért innen kiindulva elkezdünk tippelni mindaddig, míg a jobboldali kifejezésre nem négyzetszámot kapunk. A fenti példában tehát n=57\ 319\ 249\ 499. Ekkor r=239\ 414, mivel ez az a legnagyobb szám, amelynek a négyzete még nemnagyobb n-nél. Ebből kiindulva adunk tippeket a-ra, és vizsgáljuk, hogy az a^2-n négyzetszám-e: \begin{array}{c|c|c}a & a^2-n & \text{négyzetszám?} \\ \hline 239\ 415 & 292\ 726 & \text{nem} \\ 239\ 416 & 771\ 557 & \text{nem} \\ 239\ 417 & 1\ 250\ 390 & \text{nem} \\ 239\ 418 & 1\ 729\ 225 & \text{igen} \end{array} Meglepően gyorsan, mindössze 4 lépés után négyzetszámot kaptunk a második oszlopban, amely tehát b^2-tel egyezik meg. Ebből b=1315 adódik, és mivel a-t is sikerült megtippelnünk, végülis megkaptuk a két prímtényezőt is: \begin{aligned}p&=a+b=239\ 418 + 1315 = 240\ 733 \\ q&=a-b=239\ 418 - 1315=238\ 103\end{aligned} Látható, hogy eléggé hatékonyan sikerült prímtényezőire bontani a bemeneti számunkat. Mostmár látszik is, hogy miért: a két prím különbsége mindössze 2630 volt, ami nagyon kicsi a két prímhez képest. Amikor tehát Alice és Bob kulcspárt generálnak maguknak, vigyázniuk kell, hogy a kiválasztott prímszámok átlagosan az őket leíró bitek felében különbözzenek egymástól. Ezzel viszonylag hamar elvehetik Eve kedvét a fenti eljárástól, a keresett a ugyanis ebben az esetben nagyon messze lesz r-től, amelyet így az idők végezetéig keresgélhet. <h4 class="wp-block-heading">A kicsi kódoló kulcsok problémája</h4> A <a rel="noreferrer noopener" href="https://youproof.hu/kriptografia/22-kinai-maradektetel-konguenciarendszerek-kis-fermat-tetel-rsa-bizonyitas-gyuruk-direkt-szorzata-rsa-dekodolas#residue-class-ring-decomposition" target="_blank">22. részben</a> a RSA dekódolás gyorsítási lehetőségei kapcsán megemlítettük, hogy az RSA biztonsága nem függ a publikus e kódoló kitevő megválasztásától. Az ismételt négyzetreemelések módszerét vizsgálva a <a rel="noreferrer noopener" href="https://youproof.hu/kriptografia/21-rsa-algoritmus-kibovitett-euklideszi-algoritmus-euler-fuggveny-kulcsgeneralas-ismetelt-negyzetreemeles-modszere#modular-exponentiation" target="_blank">21. részben</a> megállapítottuk, hogy célszerű olyan kitevőt választani, amelynek bináris számábrázolásában kevés számú 1-es bit szerepel. Emiatt racionális megfontolásnak tűnhet, ha a megvalósítás során úgy döntünk, hogy egy viszonylag alacsony számtartományból választjuk ki a rendszer felhasználóihoz tartozó e publikus kitevőket a kulcsgenerálás során. Ez azonban bizonyos körülmények között a nyílt üzenet kiszámítására adhat lehetőséget egy támadó számára anélkül, hogy feltörné a titkosító kódolást. Tegyük fel ugyanis, hogy egy sokfelhasználós rendszerről van szó, és kicsi az a számtartomány, amelyből kisorsoljuk a felhasználók számára a publikus e kitevőt. Ekkor előfordulhat, hogy több felhasználó is ugyanazt a kitevőt kapja. Tegyük fel, hogy k darab felhasználó kapta ugyanazt az e kitevőt. Szerencsétlen, ugyanakkor nem túl ritka esetekben még az is megeshet, hogy e\leq k is teljesül. Ez látszólag nem jelent problémát, hiszen természetesen más és más prímpárokat sorsolunk hozzájuk, tehát e k darab felhasználóhoz különböző modulusok és dekódoló kitevők fognak tartozni. Képzeljük el azonban, hogy valaki egy bizalmas körlevelet küld felhasználók egy csoportjának, amelybe történetesen a fenti k darab felhasználó is beletartozik. Ebben az esetben tehát az x nyílt szöveg ugyanaz lesz. A küldő fél egyenként előkeresi a publikus kulcstárból a címzettek publikus kulcsait, és mindenki számára egyedileg kódolja az üzenetet a <a rel="noreferrer noopener" href="https://youproof.hu/kriptografia/21-rsa-algoritmus-kibovitett-euklideszi-algoritmus-euler-fuggveny-kulcsgeneralas-ismetelt-negyzetreemeles-modszere#rsa-encoding-decoding" target="_blank">21. részben</a> leírt módon. A szerencsétlenül járt k darab felhasználónak kiküldött y_1, y_2, …, y_k rejtett üzenetekből a támadó az alábbi kongruenciarendszert tudja felírni: \begin{aligned}y_1&\equiv x^e\pmod{m_1} \\ y_2&\equiv x^e\pmod{m_2} \\ &\vdots \\ y_k&\equiv x^e\pmod{m_k}\end{aligned} Ebben a kongruenciarendszerben a támadó számára egyedül az x nyílt üzenet ismeretlen, hiszen egyrészt a felhasználókhoz tartozó e kitevő és a modulusok számára is elérhetők a publikus kulcstárból, másrészt pedig az y_1, y_2, …, y_k rejtett üzeneteket a kommunikációs csatorna lehallgatásával ismeri meg. Most megmutatjuk, hogy a támadó a fent ismertetett szerencsétlen körülmények fennállása esetén ebből a kongruenciarendszerből egy pillanat alatt megkaphatja az x nyílt üzenetet. Azt mindjárt az elején feltehetjük, hogy az m_1, m_2, …, m_k modulusok páronként relatív prímek. Ezek ugyanis véletlenszerűen sorsolt prímpárok szorzataiként állnak elő, így annak gyakorlatilag nincs esélye, hogy van közöttük két olyan, amelynek közös legalább az egyik prímtényezője. Emlékeztetnénk az olvasót a kínai maradéktételhez kapcsolódó <a href="https://youproof.hu/kriptografia/22-kinai-maradektetel-konguenciarendszerek-kis-fermat-tetel-rsa-bizonyitas-gyuruk-direkt-szorzata-rsa-dekodolas/#yp-element-5985" class="yp-element-link">22.4. Tétel</a>re, valamint a <a href="https://youproof.hu/kriptografia/22-kinai-maradektetel-konguenciarendszerek-kis-fermat-tetel-rsa-bizonyitas-gyuruk-direkt-szorzata-rsa-dekodolas/#yp-element-5993" class="yp-element-link">22.5. Tétel</a>re, amelyek így már alkalmazhatók. Ezek többszöri alkalmazásával azt kapjuk, hogy a \Z/m_1\Z \times \Z/m_2\Z \times \ldots \times \Z/m_k\Z szorzatgyűrű (lásd a <a href="https://youproof.hu/kriptografia/22-kinai-maradektetel-konguenciarendszerek-kis-fermat-tetel-rsa-bizonyitas-gyuruk-direkt-szorzata-rsa-dekodolas/#yp-element-6067" class="yp-element-link">22.7. Tétel</a>t) elemei kölcsönösen egyértelmű megfeleltetésben állnak a \Z/m_1m_2\ldots m_k\Z maradékosztálygyűrű elemeivel. A fenti kongruenciarendszer a szorzatgyűrűben tulajdonképpen az alábbi elemet írja le: ([x^e]_{m_1};[x^e]_{m_2};\ldots;[x^e]_{m_k}) Ennek a \Z/m_1m_2\ldots m_k\Z maradékosztálygyűrűben a <a href="https://youproof.hu/kriptografia/22-kinai-maradektetel-konguenciarendszerek-kis-fermat-tetel-rsa-bizonyitas-gyuruk-direkt-szorzata-rsa-dekodolas/#yp-element-5993" class="yp-element-link">22.5. Tétel</a> alapján az alábbi maradékosztály felel meg: [x^e]_{m_1\cdot m_2\cdot \ldots \cdot m_k} Vegyük észre azonban, hogy az x nyílt üzenetet a küldő az előkódolás során úgy választotta meg, hogy az 0 és a legkisebb modulus közé essen. Az előkódolásról a <a rel="noreferrer noopener" href="https://youproof.hu/kriptografia/21-rsa-algoritmus-kibovitett-euklideszi-algoritmus-euler-fuggveny-kulcsgeneralas-ismetelt-negyzetreemeles-modszere#rsa-encoding-decoding" target="_blank">21. részben</a> írtunk bővebben. Teljesülnek tehát az alábbi egyenlőtlenségek: \begin{aligned}0\leq x &\lt m_1 \\ 0\leq x&\lt m_2 \\ &\vdots \\ 0\leq x &\lt m_k\end{aligned} Mivel azt mondtuk, hogy szerencsétlen módon az e\leq k egyenlőtlenség is fennáll, ezért ebben az esetben nyilván teljesül az alábbi is: 0\leq x^e \lt m_1m_2\ldots m_k Így a támadó valójában az [x^e]_{m_1m_2\ldots m_k} maradékosztály legkisebb nemnegatív reprezentánselemét kapja meg, amely nem más, mint a nyílt üzenetnek ténylegesen az e-edik hatványa – és nem pedig annak modulo megfelelője. Ebből viszont az x nyílt üzenetet már egyszerűen megkaphatja. Alice-nak és Bob-nak tehát azt javasolhatjuk, hogy a kulcsgeneráláskor semmiképpen se korlátozzák az e kitevőt egy szűk számtartományra, nehogy a fenti kellemetlenségben legyen részük. A kódolás gyorsasága szempontjából a lényeg úgyis az, hogy kevés számú 1-es legyen e bináris ábrázolásában, nem pedig az, hogy ő maga kicsi legyen. Ezen túlmenően amikor ugyanazt az üzenetet nagyszámú résztvevőnek továbbítjuk, akkor célszerű az üzenet egyes példányaiba valamilyen véletlentől függő elemet is belevinni. Például megtehetjük, hogy az utolsó valahány biten hasznos tartalom helyett elhelyezünk egy véletlenszámot. Ennek az az előnye, hogy így az eredeti x üzenet egyes példányai különböző kódolandó nyílt üzenetekké válnak, amivel a fenti támadás lehetőségét egycsapásra kiiktattuk. Természetesen ekkor a küldő és fogadó félnek meg kell egyezniük egymással, hogy melyek lesznek a haszontalan bitek. <div id="common-modulus-attack"></div> <h4 class="wp-block-heading">Közös modulus választásának hibája</h4> Végül egy nagyon súlyos potenciális rendszertervezési hibára hívnánk fel a figyelmet. Mivel az RSA meglehetősen számításigényes, ezért csábító lehet az a gondolat, hogy a teljes rendszer számára egyetlen m modulust generálunk, és csak az egyes felhasználókhoz tartozó e publikus és d titkos kitevők lesznek különbözőek a kulcsgenerálás során. Ez látszólag előnyös lehet, hiszen így például előre le tudunk gyártatni egy célhardvert, amely a modulo m maradékosztálygyűrűben való számolásra van optimalizálva. Képzeljük el, hogy az előző szakaszhoz hasonlóan ismét egy közös x üzenet – például egy körlevél – érkezik mondjuk két felhasználóhoz. Tegyük fel, hogy e két felhasználóhoz az e_1 és e_2 publikus kitevők vannak rendelve. Nagy az esély rá, hogy e két kitevő egymáshoz relatív prím, azaz (e_1,e_2)=1, és ebben az esetben egy támadó sajnos meg tudja fejteni az x nyílt üzenetet. Ő ugyanis az alábbi kongruenciákat írhatja fel: \begin{aligned}y_1&\equiv x^{e_1}\pmod m \\ y_2&\equiv x^{e_2}\pmod m\end{aligned} Ebben a kongruenciarendszerben a támadó számára ismét egyedül az x nyílt üzenet ismeretlen, hiszen az összes többi paraméter a nyilvános kulcstárból, valamint a kommunikációs csatorna lehallgatásával megismerhető. Nézzük, hogy mihez kezd mindezzel a támadó. A Bézout-lemmából (<a href="https://youproof.hu/kriptografia/21-rsa-algoritmus-kibovitett-euklideszi-algoritmus-euler-fuggveny-kulcsgeneralas-ismetelt-negyzetreemeles-modszere/#yp-element-5620" class="yp-element-link">21.1. Tétel</a>) tudjuk, hogy bármely két egész szám kitüntetett közös osztója kifejezhető a két szám lineáris kombinációjaként. Ezt jelen esetben az e_1 és e_2 kitevőkre alkalmazhatjuk. Mivel róluk azt mondtuk, hogy relatív prímek – azaz (e_1,e_2)=1 –, ezért a Bézout-lemma alapján léteznek olyan u és v egész számok, amelyekre teljesül az alábbi: (e_1,e_2)=1=u\cdot e_1 + v\cdot e_2 Ráadásul a támadó a keresett u és v egész számokat hatékonyan elő tudja állítani a kibővített euklidészi algoritmus segítségével, amelyről a <a rel="noreferrer noopener" href="https://youproof.hu/kriptografia/21-rsa-algoritmus-kibovitett-euklideszi-algoritmus-euler-fuggveny-kulcsgeneralas-ismetelt-negyzetreemeles-modszere#extended-euclidean-algorithm" target="_blank">21. részben</a> volt szó részletesen. Most vizsgáljuk meg, hogy a kiszámított u és v egész számokból, valamint a kommunikációs csatornán elfogott y_1 és y_2 kódszövegekből képzett alábbi kifejezés mivel kongruens modulo m: y_1^u\cdot y_2^v \equiv ?\pmod m Mivel y_1\equiv x^{e_1}\pmod m és y_2\equiv x^{e_2}\pmod m az RSA-kódolás alapján, ezért a kongruencia tulajdonságairól szóló <a href="https://youproof.hu/kriptografia/20-kongruencia-redukalt-maradekosztaly-euler-fuggveny-linearis-kongruencia-maradekrendszer-euler-fermat-tetel/#yp-element-5263" class="yp-element-link">20.2. Tétel</a> 8. és 5. pontjait alkalmazva ezt kapjuk: (\underbrace{x^{e_1}}_{\equiv y_1})^u\cdot (\underbrace{x^{e_2}}_{\equiv y_2})^v \equiv \ ?\pmod m A baloldali kifejezést a hatványozás azonosságairól szóló <a href="https://youproof.hu/kriptografia/18-modularis-aritmetika-homomorfizmus-kongruencia-reszgyuru-ideal-maradekosztalygyuru/#yp-element-4612" class="yp-element-link">18.8. Tétel</a> 2. és 3. pontjai alapján átírhatjuk az alábbi módon: x^{u\cdot e_1 + v\cdot e_2}\equiv \ ?\pmod m A Bézout-lemma alapján a kitevőről viszont már tudjuk, hogy az az (e_1,e_2)=1 kitüntetett közös osztóval egyezik meg, azaz teljesül az alábbi: x^{\overbrace{u\cdot e_1 + v\cdot e_2}^{=1}}\equiv x\pmod m A támadó tehát pusztán publikusan, illetve a csatorna lehallgatása által megszerezhető információkból ki tudja számítani az x nyílt szöveget anélkül, hogy feltörte volna az RSA-t. A fentiek alapján ugyanis nincs más dolga, mint kiszámítani az y_1^u\cdot y_2^v kifejezést, amely tehát biztosan az x nyílt üzenettel lesz kongruens modulo m. Felhívnánk a figyelmet azonban egy apró „csalásra”, amelyet a fenti okfejtésben elkövettünk. Vizsgáljuk meg ugyanis jobban a Bézout-lemmából kapott u\cdot e_1 + v\cdot e_2=1 egyenletet. Mivel itt az e_1 és e_2 kitevők mindketten pozitívak, ezért ebből következik, hogy u és v közül pontosan az egyik szükségképpen negatív. Ők viszont a fenti y_1^u\cdot y_2^v kifejezésben kitevőkként szerepelnek. Márpedig ebben az esetben elvileg nem használhatnánk a hatványozás azonosságairól szóló <a href="https://youproof.hu/kriptografia/18-modularis-aritmetika-homomorfizmus-kongruencia-reszgyuru-ideal-maradekosztalygyuru/#yp-element-4612" class="yp-element-link">18.8. Tétel</a>t és a kongruencia tulajdonságairól szóló <a href="https://youproof.hu/kriptografia/20-kongruencia-redukalt-maradekosztaly-euler-fuggveny-linearis-kongruencia-maradekrendszer-euler-fermat-tetel/#yp-element-5263" class="yp-element-link">20.2. Tétel</a>t, hiszen ezeket csak pozitív kitevőkre bizonyítottuk. Arról már nem is beszélve, hogy az eddigi definícióink alapján negatív kitevőket egyelőre nem is tudunk értelmezni. Ennek a kis hiányosságnak a pótlását a következő részre halasztjuk, mivel ehhez fel kell építeni néhány újabb fontos algebrai fogalmat. Ám elöljáróban megjegyezzük, hogy a hatványozás azonosságai és a kongruenciák tulajdonságai ebben a kibővített értelmezésben is érvényben fognak maradni. Így válik majd a fenti érvelés teljessé. Konklúzióként azonban elmondhatjuk, hogy a közös modulus választását mindenképpen el kell kerülni az RSA-algoritmuson alapuló kriptográfiai rendszerekben. Ebben a részben tehát főként azzal a problémával foglalkoztunk, hogy hogyan tud Alice és Bob az RSA-kulcsgeneráláshoz szükséges óriási prímszámokat találni. Ennek keretében megmutattuk, hogy a hagyományos, osztáspróbákon alapuló módszer a gyakorlatban a lassúsága miatt nem alkalmazható. Ezért bemutattunk két valószínűségi prímtesztet, amelyek a kis Fermat-tételen alapulnak. Az első a Fermat-prímteszt volt, amelynek fő hátránya, hogy léteznek olyan összetett számok, amelyeket nem tud kiszűrni. Ezeket univerzális álprímeknek vagy Carmichael-számoknak nevezzük, amelyekről a közelmúltban kimutatták, hogy sajnos végtelen sok van belőlük. Ezt a problémát kiküszöbölendő bemutattuk a Miller-Rabin-prímtesztet, amely – úgy tűnik – kiszűri az univerzális álprímeket is. Végül felhívtuk a figyelmet pár olyan dologra, amelyekre Alice-nak és Bob-nak oda kell figyelniük a kulcsgenerálás során. A következő részben megismerkedünk az absztrakt algebra talán legfontosabb ágának, az úgynevezett csoportelméletnek az alapjaival. Ezután az így felépített eszközök segítségével igazolni fogjuk, hogy a Miller-Rabin-prímtesztre nézve valóban nem léteznek univerzális álprímek. Végül adunk egy felső korlátot is annak valószínűségére, hogy egy összetett számot tévesen prímmé nyilvánít ez a teszt. A következő részt <a href="https://youproof.hu/kriptografia/24-csoport-reszcsoport-mellekosztaly-lagrange-tetel-csoport-rendje-elem-rendje-miller-rabin-primteszt/">itt</a> találod… </div>   <div class="fb-like" data-href="https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/" data-width="100" data-layout="button" data-action="like" data-size="large" data-show-faces="false" data-share="true"></div>   <div class="yp-facebook-follow"> <a class="button" href="https://www.facebook.com/youproof.hu" target="_blank">Látogass el Facebook-oldalunkra!</a> </div>  </article>  <div class="yp-ads"> <h5>Kapcsolódó oldal:</h5> <a href="http://ematlap.hu" target="_blank"> <img src="https://youproof.hu/wp-content/themes/minimum-minimal-child/assets/images/erinto_logo.png" width="85%" height="85%" alt="Érintő - Elektronikus Matematikai Lapok"> </a> </div>  <div class="entry-meta cat-and-tags"> <div id="categories"> <a href="https://youproof.hu/kategoria/elemi-szamelmelet/" rel="category tag">Elemi számelmélet</a></div> <div id="tags"> <a href="https://youproof.hu/cimke/asszocialt/" rel="tag">asszociált</a>, <a href="https://youproof.hu/cimke/bezout-lemma/" rel="tag">Bézout-lemma</a>, <a href="https://youproof.hu/cimke/carmichael-szam/" rel="tag">Carmichael-szám</a>, <a href="https://youproof.hu/cimke/egyseg/" rel="tag">egység</a>, <a href="https://youproof.hu/cimke/euklideszi-algoritmus/" rel="tag">euklidészi algoritmus</a>, <a href="https://youproof.hu/cimke/felbonthatatlan/" rel="tag">felbonthatatlan</a>, <a href="https://youproof.hu/cimke/fermat-faktorizacio/" rel="tag">Fermat-faktorizáció</a>, <a href="https://youproof.hu/cimke/fermat-primteszt/" rel="tag">Fermat-prímteszt</a>, <a href="https://youproof.hu/cimke/kinai-maradektetel/" rel="tag">kínai maradéktétel</a>, <a href="https://youproof.hu/cimke/kis-fermat-tetel/" rel="tag">kis Fermat-tétel</a>, <a href="https://youproof.hu/cimke/kongruencia/" rel="tag">kongruencia</a>, <a href="https://youproof.hu/cimke/kongruenciarendszer/" rel="tag">kongruenciarendszer</a>, <a href="https://youproof.hu/cimke/maradekosztaly/" rel="tag">maradékosztály</a>, <a href="https://youproof.hu/cimke/miller-rabin-primteszt/" rel="tag">Miller-Rabin-prímteszt</a>, <a href="https://youproof.hu/cimke/prim/" rel="tag">prím</a>, <a href="https://youproof.hu/cimke/primteszt/" rel="tag">prímteszt</a>, <a href="https://youproof.hu/cimke/relativ-prim/" rel="tag">relatív prím</a>, <a href="https://youproof.hu/cimke/univerzalis-alprim/" rel="tag">univerzális álprím</a></div> </div> </div> <div class="row"> <div class="large-7 medium-8 small-11 small-centered columns"> <div id="above-comments-widget-area" class="widget-area" role="complementary"> <aside class="widget_text row widget"><div id="custom_html-2" class="widget_text medium-12 columns widget_custom_html"><h2 class="widget-title">Add meg az email címed, hogy értesülhess a legújabb tartalmakról!</h2><div class="textwidget custom-html-widget"><div id="mc_embed_signup" class="medium-12"> <form action="https://youproof.us20.list-manage.com/subscribe/post?u=fb18d5fa12302b3158f19d229&id=e596e966ba" method="post" id="mc-embedded-subscribe-form" name="mc-embedded-subscribe-form" class="validate" target="_blank"> <div id="mc_embed_signup_scroll"> <div class="mc-field-group"> <label for="mce-EMAIL">Email cím</label> <input type="email" value="" name="EMAIL" class="required email" id="mce-EMAIL" required="true"/> <label> <input name="AGREE_TO_TERMS" type="checkbox" value="1" required="true"> <a href="https://youproof.hu/adatkezeles/" target="_blank" rel="noopener">Elolvastam és elfogadom a felhasználási feltételeket</a> </label> </div> <div id="mce-responses" class="clear"> <div class="response" id="mce-error-response" style="display:none"></div> <div class="response" id="mce-success-response" style="display:none"></div> </div>  <div style="position: absolute; left: -5000px;" aria-hidden="true"> <input type="text" name="b_fb18d5fa12302b3158f19d229_e596e966ba" tabindex="-1" value=""> </div> <div class="clear"> <input type="submit" value="Feliratkozok" name="subscribe" id="mc-embedded-subscribe" class="button"> </div> </div> </form> </div></div></div></aside> </div> <div id="comments" class="comments-area"> <div id="respond" class="comment-respond"> <h3 id="reply-title" class="comment-reply-title">Vélemény, hozzászólás? <a rel="nofollow" id="cancel-comment-reply-link" href="/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio/#respond" style="display:none;">Válasz megszakítása</a></h3><form action="https://youproof.hu/wp-comments-post.php" method="post" id="commentform" class="comment-form" novalidate>Az e-mail címet nem tesszük közzé. A kötelező mezőket * karakterrel jelöltük<label for="comment">Hozzászólás *</label> <textarea id="comment" name="comment" cols="45" rows="8" maxlength="65525" required></textarea><label for="author">Név *</label> <input id="author" name="author" type="text" value="" size="30" maxlength="245" autocomplete="name" required /> <label for="email">E-mail cím *</label> <input id="email" name="email" type="email" value="" size="30" maxlength="100" aria-describedby="email-notes" autocomplete="email" required /> <label for="url">Honlap</label> <input id="url" name="url" type="url" value="" size="30" maxlength="200" autocomplete="url" /> <input name="submit" type="submit" id="submit" class="submit button" value="Hozzászólás küldése" /> <input type='hidden' name='comment_post_ID' value='6204' id='comment_post_ID' /> <input type='hidden' name='comment_parent' id='comment_parent' value='0' /> <input type="hidden" id="akismet_comment_nonce" name="akismet_comment_nonce" value="076de30e9f" /><label>Δ<textarea name="ak_hp_textarea" cols="45" rows="8" maxlength="100"></textarea></label><input type="hidden" id="ak_js_1" name="ak_js" value="6"/><script>document.getElementById( "ak_js_1" ).setAttribute( "value", ( new Date() ).getTime() );</script></form> </div> </div> </div> </div> </div>  <footer id="site-footer" > <div id="footermenu" class="row"> <div class="columns"> <div class="menu footernav"><ul id="footer-navigation" class="menu"><li id="menu-item-36" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-36"><a href="https://youproof.hu/impresszum/">Impresszum</a></li> <li id="menu-item-40" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-40"><a href="https://youproof.hu/suti-cookie-kezelese/">Süti-Cookie</a></li> <li id="menu-item-58" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-privacy-policy menu-item-58"><a rel="privacy-policy" href="https://youproof.hu/adatkezeles/">Adatkezelés</a></li> <li id="menu-item-65" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-65"><a href="https://youproof.hu/jogi-nyilatkozat/">Jogi nyilatkozat</a></li> </ul></div> </div> </div> <div id="copyright" class="row"> <div class="columns"> © 2024 YOUPROOF - Minden jog fenntartva </div> <div class="columns">v1.2.2</div> </div> <link rel='stylesheet' id='katex-css' href='https://youproof.hu/wp-content/plugins/wp-katex/assets/katex.min.css?ver=0.11.0' type='text/css' media='all' /> <script type="text/javascript" id="cookie-notice-front-js-before"> /* <![CDATA[ */ var cnArgs = {"ajaxUrl":"https:\/\/youproof.hu\/wp-admin\/admin-ajax.php","nonce":"162003720d","hideEffect":"fade","position":"bottom","onScroll":false,"onScrollOffset":100,"onClick":false,"cookieName":"cookie_notice_accepted","cookieTime":2592000,"cookieTimeRejected":2592000,"globalCookie":false,"redirection":false,"cache":false,"revokeCookies":false,"revokeCookiesOpt":"automatic"}; /* ]]> */ </script> <script type="text/javascript" src="https://youproof.hu/wp-content/plugins/cookie-notice/js/front.min.js?ver=2.4.16" id="cookie-notice-front-js"></script> <script type="text/javascript" src="https://youproof.hu/wp-content/themes/minimum-minimal/assets/js/app.js?ver=1.0" id="minimumminimal-main-js"></script> <script type="text/javascript" src="https://youproof.hu/wp-content/themes/minimum-minimal/foundation.js?ver=1" id="minimumminimal-foundation-init-js-js"></script> <script type="text/javascript" src="https://youproof.hu/wp-includes/js/comment-reply.min.js?ver=6.5.5" id="comment-reply-js" async="async" data-wp-strategy="async"></script> <script type="text/javascript" src="https://youproof.hu/wp-content/plugins/youproof-plugin/js/yp-element-expander.js?ver=1.0" id="yp-element-script-js"></script> <script type="text/javascript" src="https://youproof.hu/wp-content/plugins/wp-katex/assets/katex.min.js?ver=0.11.0" id="katex-js"></script> <script defer type="text/javascript" src="https://youproof.hu/wp-content/plugins/akismet/_inc/akismet-frontend.js?ver=1713534996" id="akismet-frontend-js"></script> <script>!function(){"use strict";for(var e=document.querySelectorAll(".wp-katex-eq"),t=0;t<e.length;t++){var r=e[t],a=document.createElement("span");try{katex.render(r.textContent,a,{displayMode:"true"===r.getAttribute("data-display"),throwOnError:!1})}catch(n){a.style.color="red",a.textContent=n.message}r.parentNode.replaceChild(a,r)}}();</script>  <div id="cookie-notice" role="dialog" class="cookie-notice-hidden cookie-revoke-hidden cn-position-bottom" aria-label="Cookie Notice" style="background-color: rgba(0,0,0,1);"><div class="cookie-notice-container" style="color: #fff">Kedves Látogató! Tájékoztatjuk, hogy a felhasználói élmény fokozásának érdekében sütiket alkalmazunk. A honlapunk használatával ön a tájékoztatásunkat tudomásul veszi.<a href="#" id="cn-accept-cookie" data-cookie-set="accept" class="cn-set-cookie cn-button cn-button-custom button" aria-label="Elfogadom">Elfogadom</a><a href="https://youproof.hu/suti-cookie-kezelese/" target="_blank" id="cn-more-info" class="cn-more-info cn-button cn-button-custom button" aria-label="Tájékoztató">Tájékoztató</a></div> </div>  </body> </html>