yuvalmadar
New member
בכלליות, צריך עבור p<q
ראשוניים לדאוג שp יחלק את q-1.
ראשוניים לדאוג שp יחלק את q-1.
אתה משתמש בדפדפן מיושן. יתכן והאתר הנוכחי יוצג באופן שגוי, כמו כן אתרים אחרים ברשת.
אנא שדרג את הדפדפן או השתמש בדפדפן חילופי.
אנא שדרג את הדפדפן או השתמש בדפדפן חילופי.
שאלה לגבי אלגוריתם RSA
- פותח הנושא theuser1
- פורסם בתאריך
yuvalmadar
New member
הוכחה נוספת
(הוכחה בכיוון השני - קיימים PQ מספרים טבעיים הקטנים/שווים לpq, ובדיוק p+q-1 מהם לא זרים לpq) נתבונן בPQ המספרים הטבעיים הראשונים. איזה מהם אינו זר לPQ? מספר אשר p או q מחלקים אותו. (לפי המשפט היסודי של האריתמטיקה למשל. (לכל מספר קיים פירוק יחיד למכפלת מספרים ראשוניים)) ואיזה מספרים מתחלקים בp וקטנים מpq?
(הוכחה בכיוון השני - קיימים PQ מספרים טבעיים הקטנים/שווים לpq, ובדיוק p+q-1 מהם לא זרים לpq) נתבונן בPQ המספרים הטבעיים הראשונים. איזה מהם אינו זר לPQ? מספר אשר p או q מחלקים אותו. (לפי המשפט היסודי של האריתמטיקה למשל. (לכל מספר קיים פירוק יחיד למכפלת מספרים ראשוניים)) ואיזה מספרים מתחלקים בp וקטנים מpq?
p, 2p, ..., qp
ואיזה מספרים מתחלקים בq וקטנים מpq?q, 2q, ..., qp
סה"כ, מדובר בp+q-1 מספרים שאינם זרים לpq. (המינוס נובע מכך שספרתי את pq פעמיים - ככפולה של p וככפולה של q) לכן, מספר המספרים הזרים לpq הוא -pq - p - q + 1 = (q-1)(p-1)
כרצוי.r=(p-1)(q-1) PROD=p*q
(s,p*q) = 1 <=> there is b such that b|s and b|p*q since we are checking ALL numbers between 1 and p*q, it is enough to ask that s|p*q (why? because if b|s and b|p*q then b is of the form n*p or q*n hence s=n'*p or s=n'*q hence s |p*q) so now let's find for how many numbers a|p*q a | p*q <=> a = p*n or a = q*m when m,n natural n<=q m<=p <=> a is in A1 = {p*n | n <= q } |A1| = q a is in A2 = {q*n | n <= p } |A2| = p |A1 intersection A2| = 1 (only p*q is in the intersection) so |A1 U A2| = p + q - 1 hence the result is p*q (all numbers) minus numbers which divide p*q which counts to: p*q - p - q + 1 and indeed (p-1)(q-1) = p*q - p - q + 1 דרך קלה יותר בהסתמך על פונקצית אוילר: euler(p*q) = euler(p)euler(q) = (p-1)(q-1) וזה בגלל שפונקצית אוילר ניתנת לפירוק ביחס למכפלה של מספרים זרים (פונקצית אוילר עבור מספר מסוים היא מספר המספרים הזרים למספר בין 1 לאותו מספר) מצטער שזה באנגלית בהתחלה, אחרת כל הטקסט מתבלבל.
(s,p*q) = 1 <=> there is b such that b|s and b|p*q since we are checking ALL numbers between 1 and p*q, it is enough to ask that s|p*q (why? because if b|s and b|p*q then b is of the form n*p or q*n hence s=n'*p or s=n'*q hence s |p*q) so now let's find for how many numbers a|p*q a | p*q <=> a = p*n or a = q*m when m,n natural n<=q m<=p <=> a is in A1 = {p*n | n <= q } |A1| = q a is in A2 = {q*n | n <= p } |A2| = p |A1 intersection A2| = 1 (only p*q is in the intersection) so |A1 U A2| = p + q - 1 hence the result is p*q (all numbers) minus numbers which divide p*q which counts to: p*q - p - q + 1 and indeed (p-1)(q-1) = p*q - p - q + 1 דרך קלה יותר בהסתמך על פונקצית אוילר: euler(p*q) = euler(p)euler(q) = (p-1)(q-1) וזה בגלל שפונקצית אוילר ניתנת לפירוק ביחס למכפלה של מספרים זרים (פונקצית אוילר עבור מספר מסוים היא מספר המספרים הזרים למספר בין 1 לאותו מספר) מצטער שזה באנגלית בהתחלה, אחרת כל הטקסט מתבלבל.
מצטער, עשיתי טעות
אני מצטער, עשיתי טעות בהודעה הקודמת ההוכחה הנכונה היא
אני מצטער, עשיתי טעות בהודעה הקודמת ההוכחה הנכונה היא
(a,p*q) not equal 1 (we will find first how many numbers are not zarim to p*q and then do p*q minus that number) <=> a = p*n or a = q*m when m,n natural n<=q m<=p <=> a is in A1 = {p*n | n <= q } |A1| = q a is in A2 = {q*n | n <= p } |A2| = p |A1 intersection A2| = 1 (only p*q is in the intersection) so |A1 U A2| = p + q - 1 hence the result is p*q (all numbers) minus numbers which divide p*q which counts to: p*q - p - q + 1 and indeed (p-1)(q-1) = p*q - p - q + 1
Copyright©1996-2021,Tapuz Media Ltd. Forum software by XenForo® © 2010-2020 XenForo Ltd.