משתמש:איתמר שטיין/הסבר הופכי - היסטוריית גרסאות

איתמר שטיין: /* כמה מושגים בתורת המספרים */

2012-07-12T18:02:25Z

כמה מושגים בתורת המספרים

→ הגרסה הקודמת		גרסה מ־18:02, 12 ביולי 2012
שורה 35:		שורה 35:
	<math>(na+mp)mod~p = 1mod~p</math>		<math>(na+mp)mod~p = 1mod~p</math>
	שהופך ל <math>(na)mod~p = 1</math>		שהופך ל <math>(na)mod~p = 1</math>
	לכן <math>n~mod~p</math> הוא ~~הפכי~~ מתאים ל <math>a</math>.		לכן <math>n~mod~p</math> הוא הופכי מתאים ל <math>a</math>.

	כל זה טוב ויפה, אבל איך מוצאים את <math>n</math>?		כל זה טוב ויפה, אבל איך מוצאים את <math>n</math>?

איתמר שטיין: /* חישוב ההופכי */

2012-07-12T18:00:47Z

חישוב ההופכי

→ הגרסה הקודמת		גרסה מ־18:00, 12 ביולי 2012
שורה 98:		שורה 98:


	* אם <math>b<0</math> או <math>a<0</math> אז מוצאים <math>n',m'</math> מתאימים עבור <math>\|a\|,\|b\|</math>		* אם <math>b<0</math> או <math>a<0</math> אז מוצאים <math>n',m'</math> מתאימים עבור <math>\|a\|,\|b\|</math> בשיטה שתוארה קודם

	ואז <math>n'\|a\|+m'\|b\|=1</math> ואז		ואז <math>n'\|a\|+m'\|b\|=1</math> ואז

איתמר שטיין: /* חישוב ההופכי */

2012-07-12T17:59:44Z

חישוב ההופכי

→ הגרסה הקודמת		גרסה מ־17:59, 12 ביולי 2012
שורה 80:		שורה 80:
	שהופך ל:		שהופך ל:
	<math>(1+q_{k-1}q_{k-2})r_{k-2}-q_{k-1}r_{k-3} = 1</math> <math>(\ast)</math>		<math>(1+q_{k-1}q_{k-2})r_{k-2}-q_{k-1}r_{k-3} = 1</math> <math>(\ast)</math>


	אבל שוב, בשלב קודם ראינו ש		אבל שוב, בשלב קודם ראינו ש
שורה 85:		שורה 86:

	ואפשר להציב את <math>r_{k-4} - q_{k-3}r_{k-3}</math> ב <math>r_{k-2}</math>		ואפשר להציב את <math>r_{k-4} - q_{k-3}r_{k-3}</math> ב <math>r_{k-2}</math>

	שמופיע בביטוי <math>(\ast)</math> ולקבל ביטוי מהצורה		שמופיע בביטוי <math>(\ast)</math> ולקבל ביטוי מהצורה

איתמר שטיין: /* חישוב ההופכי */

2012-07-12T17:58:24Z

חישוב ההופכי

→ הגרסה הקודמת		גרסה מ־17:58, 12 ביולי 2012
שורה 83:		שורה 83:
	אבל שוב, בשלב קודם ראינו ש		אבל שוב, בשלב קודם ראינו ש
	<math>r_{k-4} - q_{k-3}r_{k-3} =r_{k-2}</math>		<math>r_{k-4} - q_{k-3}r_{k-3} =r_{k-2}</math>
	ואפשר להציב את ~~התוצאה~~ ב
	<math>r_{k-2}</math>		ואפשר להציב את <math>r_{k-4} - q_{k-3}r_{k-3}</math> ב <math>r_{k-2}</math>

	שמופיע בביטוי <math>(\ast)</math> ולקבל ביטוי מהצורה		שמופיע בביטוי <math>(\ast)</math> ולקבל ביטוי מהצורה

	<math>xr_{k-4}+yr_{k-3}=1</math>		<math>xr_{k-4}+yr_{k-3}=1</math>
			עבור <math>x,y</math> כלשהם

	וכן הלאה עד שנגיע לביטוי מהצורה		וכן הלאה עד שנגיע לביטוי מהצורה

איתמר שטיין: /* חישוב ההופכי */

2012-07-12T17:56:24Z

חישוב ההופכי

→ הגרסה הקודמת		גרסה מ־17:56, 12 ביולי 2012
שורה 66:		שורה 66:
	עד כאן החלק הקל,		עד כאן החלק הקל,
	עכשיו צריך להתחיל חישוב אחורה		עכשיו צריך להתחיל חישוב אחורה


			השלב האחרון שהגענו אליו היה

	<math>r_{k-2}-q_{k-1}r_{k-1} = r_k = 1</math>		<math>r_{k-2}-q_{k-1}r_{k-1} = r_k = 1</math>

איתמר שטיין: /* חישוב ההופכי */

2012-07-12T17:52:37Z

חישוב ההופכי

→ הגרסה הקודמת		גרסה מ־17:52, 12 ביולי 2012
שורה 60:		שורה 60:

	נמשיך כך עד שנגיע לשלב <math>k</math> שבו <math>r_k=1</math>.		נמשיך כך עד שנגיע לשלב <math>k</math> שבו <math>r_k=1</math>.

			(היות ו <math>gcd(a,b)=1</math> מובטח לנו שנגיע מתישהוא ל <math>1</math>)


שורה 98:		שורה 100:
	אם <math>b<0</math> לוקחים <math>m=-m'</math> (אחרת <math>m=m'</math>)		אם <math>b<0</math> לוקחים <math>m=-m'</math> (אחרת <math>m=m'</math>)

	* אם <math>a=0</math> הסיכוי היחיד ש <math>gcd(a,b)=1</math> זה אם <math>b=1</math> וזה מקרה פשוט
			* אם <math>a=0</math> הסיכוי היחיד ש <math>gcd(a,b)=1</math> זה אם <math>b=1</math> או <math>b=-1</math> וזה מקרה פשוט

	כנ"ל אם <math>b=0</math>		כנ"ל אם <math>b=0</math>

איתמר שטיין: /* חישוב ההופכי */

2012-07-12T17:49:23Z

חישוב ההופכי

→ הגרסה הקודמת		גרסה מ־17:49, 12 ביולי 2012
שורה 45:		שורה 45:


	נתחיל מהמקרה <math>a,b>0</math>		* נתחיל מהמקרה <math>a,b>0</math>

	נניח ש <math>b>a</math>, נסמן <math>r_1=b \quad r_2 = a</math>.		נניח ש <math>b>a</math>, נסמן <math>r_1=b \quad r_2 = a</math>.
שורה 90:		שורה 90:


	אם <math>b<0</math> או <math>a<0</math> אז מוצאים <math>n',m'</math> מתאימים עבור <math>\|a\|,\|b\|</math>		* אם <math>b<0</math> או <math>a<0</math> אז מוצאים <math>n',m'</math> מתאימים עבור <math>\|a\|,\|b\|</math>

	ואז <math>n'\|a\|+m'\|b\|=1</math> ואז		ואז <math>n'\|a\|+m'\|b\|=1</math> ואז
שורה 98:		שורה 98:
	אם <math>b<0</math> לוקחים <math>m=-m'</math> (אחרת <math>m=m'</math>)		אם <math>b<0</math> לוקחים <math>m=-m'</math> (אחרת <math>m=m'</math>)

	(אם <math>a=0</math> הסיכוי היחיד ש <math>gcd(a,b)=1</math> זה אם <math>b=1</math> וזה מקרה פשוט		* אם <math>a=0</math> הסיכוי היחיד ש <math>gcd(a,b)=1</math> זה אם <math>b=1</math> וזה מקרה פשוט

	כנ"ל אם <math>b=0</math>)		כנ"ל אם <math>b=0</math>

	== דוגמא ==		== דוגמא ==

איתמר שטיין: /* חישוב ההופכי */

2012-07-12T17:48:09Z

חישוב ההופכי

→ הגרסה הקודמת		גרסה מ־17:48, 12 ביולי 2012
שורה 90:		שורה 90:


	אם <math>a,b<0</math> אז מוצאים <math>n,m</math> מתאימים עבור <math>\|a\|,\|b\|</math>		אם <math>b<0</math> או <math>a<0</math> אז מוצאים <math>n',m'</math> מתאימים עבור <math>\|a\|,\|b\|</math>

	ואז <math>~~(-n)a+(-m)b=~~n\|a\|+m\|b\|=1</math> ~~אז פשוט~~ לוקחים את <math>-n,-m</math>.		ואז <math>n'\|a\|+m'\|b\|=1</math> ואז

			אם <math>a<0</math> לוקחים <math>n=-n'</math> (אחרת <math>n=n'</math>)

			אם <math>b<0</math> לוקחים <math>m=-m'</math> (אחרת <math>m=m'</math>)

			(אם <math>a=0</math> הסיכוי היחיד ש <math>gcd(a,b)=1</math> זה אם <math>b=1</math> וזה מקרה פשוט

			כנ"ל אם <math>b=0</math>)

	== דוגמא ==		== דוגמא ==

איתמר שטיין: /* כמה מושגים בתורת המספרים */

2012-07-12T17:42:09Z

כמה מושגים בתורת המספרים

→ הגרסה הקודמת		גרסה מ־17:42, 12 ביולי 2012
שורה 23:		שורה 23:
	ההגדרה הזאת בעייתית כאשר <math>a=b=0</math> במצב זה אומרים ש <math>gcd(0,0)=0</math>.		ההגדרה הזאת בעייתית כאשר <math>a=b=0</math> במצב זה אומרים ש <math>gcd(0,0)=0</math>.

	נשים לב שאם <math>p</math> מספר ראשוני ו <math>1\~~geq~~ a\~~geq~~ p-1</math> אז <math>gcd(a,p)=1</math>		נשים לב שאם <math>p</math> מספר ראשוני ו <math>1\leq a\leq p-1</math> אז <math>gcd(a,p)=1</math>


שורה 38:		שורה 38:

	כל זה טוב ויפה, אבל איך מוצאים את <math>n</math>?		כל זה טוב ויפה, אבל איך מוצאים את <math>n</math>?

	== חישוב ההופכי ==		== חישוב ההופכי ==

איתמר שטיין ב־17:41, 12 ביולי 2012

2012-07-12T17:41:07Z

→ הגרסה הקודמת		גרסה מ־17:41, 12 ביולי 2012
שורה 1:		שורה 1:
	כאשר אנו מבצעים חישובים בשדה <math>\mathbb{Z}_p</math> (נזכור ש <math>p</math> חייב להיות ראשוני), אנו נדרשים לפעמים לחשב הופכי לאיבר מסוים בשדה.		כאשר אנו מבצעים חישובים בשדה <math>\mathbb{Z}_p</math> (נזכור ש <math>p</math> חייב להיות ראשוני), אנו נדרשים לפעמים לחשב הופכי לאיבר מסוים בשדה.

	שיטה אחת לבצע זאת היא ע"י ~~ניחוש~~,		שיטה אחת לבצע זאת היא ע"י מעבר על כל האפשרויות,
	אם <math>a\in \mathbb{Z}_p</math> אז יש <math>p</math> איברים שיכולים להיות הופכי: <math>\{0,1,\ldots,p-1\}</math>		אם <math>a\in \mathbb{Z}_p</math> אז יש <math>p</math> איברים שיכולים להיות הופכי: <math>\{0,1,\ldots,p-1\}</math>