מבנים אלגבריים למדעי המחשב - ארז שיינר - היסטוריית גרסאות

ארז שיינר: /* הרצאה 4 הומומורפיזמים, איזומורפיזמים, משפט קיילי, משפט לגראנג'; פרקים 9 ו6 מהספר */

2026-05-07T07:52:06Z

הרצאה 4 הומומורפיזמים, איזומורפיזמים, משפט קיילי, משפט לגראנג'; פרקים 9 ו6 מהספר

→ הגרסה הקודמת		גרסה מ־07:52, 7 במאי 2026
שורה 246:		שורה 246:
	***לכן <math>f(a^n)=\left(f(a)\right)^n=e_H</math>.		***לכן <math>f(a^n)=\left(f(a)\right)^n=e_H</math>.
	***לכן <math>o(f(a))\leq n=o(a)</math>.		***לכן <math>o(f(a))\leq n=o(a)</math>.
			**אם f איזומורפיזם אזי גם <math>f^{-1}</math> איזומורפיזם
	**אם f איזומורפיזם אזי <math>o(f(a))= o(a)</math>.		**אם f איזומורפיזם אזי <math>o(f(a))= o(a)</math>.
	***~~נניח כי <math>o(a)=n</math>, הוכחנו ש~~<math>o(f(a))\leq n</math>.		***<math>o(f(a))\leq o(a)</math>
	***~~נסמן~~ <math>o(f(a))=~~k</math>.~~		***<math>o(a)= o(f^{-1}(f(a)))\leq o(f(a))</math>
	***לכן <math>\left(f(~~a)\right)^k=e_H</math>, ולכן <math>~~f(a^k)~~=e_H</math>.~~
	***כיוון שאיזומורפיזם הינו פונקציה חח"ע, נובע כי <math>a^k=e_G</math>, כלומר <math>o(a)\leq ~~k</math>.~~
	***ביחד <math>k=n</math>.
	***לבסוף, נובע <math>o(f(a))</math> ~~סופי אם"ם <math>o(a)</math> סופי, ולכן הם שווים גם אם אחד מהם הוא אינסוף.~~
	**אם f הומומורפיזם אזי <math>f(a^{-1})=\left(f(a)\right)^{-1}</math> (שימו לב שf לא צריכה להיות הפיכה, והסימון <math>f^{-1}(a)</math> לא בהכרח מוגדר ואינו קשור).		**אם f הומומורפיזם אזי <math>f(a^{-1})=\left(f(a)\right)^{-1}</math> (שימו לב שf לא צריכה להיות הפיכה, והסימון <math>f^{-1}(a)</math> לא בהכרח מוגדר ואינו קשור).
	***אכן <math>f(a)\cdot f(a^{-1})=f(e_G)=e_H</math>.		***אכן <math>f(a)\cdot f(a^{-1})=f(e_G)=e_H</math>.

ארז שיינר: /* סימן של תמורה */

2026-04-16T06:44:21Z

סימן של תמורה

ארז שיינר: /* ספר הקורס */

2026-03-12T15:03:49Z

ספר הקורס

→ הגרסה הקודמת		גרסה מ־15:03, 12 במרץ 2026
שורה 2:		שורה 2:

	=ספר הקורס=		=ספר הקורס=
	ההרצאות מבוססות באופן כללי על הספר [~~https~~://abstract.ups.edu/aata/ Abstarct Algebra - Theory and Applications by Thomas W. Judson]		ההרצאות מבוססות באופן כללי על הספר [http://abstract.ups.edu/aata/ Abstarct Algebra - Theory and Applications by Thomas W. Judson]

ארז שיינר: /* ספר הקורס */

2026-03-12T15:03:15Z

ספר הקורס

→ הגרסה הקודמת		גרסה מ־15:03, 12 במרץ 2026
שורה 2:		שורה 2:

	=ספר הקורס=		=ספר הקורס=
	ההרצאות מבוססות באופן כללי על הספר [~~http~~://abstract.ups.edu/aata/ Abstarct Algebra - Theory and Applications by Thomas W. Judson]		ההרצאות מבוססות באופן כללי על הספר [https://abstract.ups.edu/aata/ Abstarct Algebra - Theory and Applications by Thomas W. Judson]

ארז שיינר: /* דיפי-הלמן */

2023-10-22T16:07:08Z

דיפי-הלמן

→ הגרסה הקודמת		גרסה מ־16:07, 22 באוקטובר 2023
שורה 483:		שורה 483:
	מומלץ לקרוא ישירות את המאמר פורץ הדרך בו הוצגה השיטה:		מומלץ לקרוא ישירות את המאמר פורץ הדרך בו הוצגה השיטה:

	[http://~~static~~.~~cs.brown~~.edu/~~courses/csci1510~~/~~reference~~/~~diffie_hellman_paper~~.pdf Diffie, Whitfield, and Martin E. Hellman. "New directions in cryptography."]		[http://ee.stanford.edu/%7Ehellman/publications/24.pdf Diffie, Whitfield, and Martin E. Hellman. "New directions in cryptography."]

ארז שיינר: /* דיפי-הלמן */

2023-05-28T14:04:45Z

דיפי-הלמן

→ הגרסה הקודמת		גרסה מ־14:04, 28 במאי 2023
שורה 481:		שורה 481:

	===דיפי-הלמן===		===דיפי-הלמן===
			מומלץ לקרוא ישירות את המאמר פורץ הדרך בו הוצגה השיטה:

			[http://static.cs.brown.edu/courses/csci1510/reference/diffie_hellman_paper.pdf Diffie, Whitfield, and Martin E. Hellman. "New directions in cryptography."]


	*למדנו שבעזרת RSA ניתן להעביר פיסת מידע באופן בטוח בערוץ פומבי, ולרוב נרצה להעביר מפתח סודי לצורך הצפנה סימטרית.		*למדנו שבעזרת RSA ניתן להעביר פיסת מידע באופן בטוח בערוץ פומבי, ולרוב נרצה להעביר מפתח סודי לצורך הצפנה סימטרית.
	*אלגוריתם דיפי-הלמן הוא שיטה לתיאום מפתח סודי בלבד ולא להעברת מידע.		*אלגוריתם דיפי-הלמן הוא שיטה לתיאום מפתח סודי בלבד ולא להעברת מידע.

ארז שיינר: /* RSA */

2023-05-28T14:01:41Z

RSA

→ הגרסה הקודמת		גרסה מ־14:01, 28 במאי 2023
שורה 403:		שורה 403:

	===RSA===		===RSA===

			מומלץ לקרוא ישירות את המאמר פורץ הדרך בו הוצגה השיטה:

			[https://people.cs.umass.edu/~emery/classes/cmpsci691st/readings/Sec/Rsapaper.pdf Rivest, Ronald L., Adi Shamir, and Leonard Adleman. "A method for obtaining digital signatures and public-key cryptosystems."]


	*אליס בוחרת שני ראשוניים גדולים <math>\{p,q\}</math> זה הסוד שלה.		*אליס בוחרת שני ראשוניים גדולים <math>\{p,q\}</math> זה הסוד שלה.
	*אליס מחשבת את המכפלה <math>n=p\cdot q</math>		*אליס מחשבת את המכפלה <math>n=p\cdot q</math>

ארז שיינר: /* מבחנים לדוגמא */

2023-02-02T06:19:07Z

מבחנים לדוגמא

→ הגרסה הקודמת		גרסה מ־06:19, 2 בפברואר 2023
שורה 30:		שורה 30:
	*[[מדיה:21ASTestC.pdf\|מבחן מועד ג' תשפ"א]]		*[[מדיה:21ASTestC.pdf\|מבחן מועד ג' תשפ"א]]
	*[[מדיה:22ASTestA.pdf\|מבחן מועד א' תשפ"ב]]		*[[מדיה:22ASTestA.pdf\|מבחן מועד א' תשפ"ב]]
			*[[מדיה:22ASTestB.pdf\|מבחן מועד ב' תשפ"ב]]

Erez1: /* חלוקה עם שארית */

2022-12-01T08:04:45Z

חלוקה עם שארית

→ הגרסה הקודמת		גרסה מ־08:04, 1 בדצמבר 2022
שורה 332:		שורה 332:
	***נניח <math>b=q_1a+r_1=q_2a+r_2</math>.		***נניח <math>b=q_1a+r_1=q_2a+r_2</math>.
	***לכן <math>(q_1-q_2)a=r_2-r_1</math>.		***לכן <math>(q_1-q_2)a=r_2-r_1</math>.
	***אבל <math>-(a-1)<r_2-r_2<a-1</math>, ולכן <math>r_2-r_1\neq ka</math>.		***אבל <math>-(a-1)\leq r_2-r_2\leq a-1</math>, ולכן <math>r_2-r_1\neq ka</math>.
	***לכן <math>q_1-q_2=0</math> כלומר <math>q_1=q_2</math> ולכן גם <math>r_1=r_2</math>.		***לכן <math>q_1-q_2=0</math> כלומר <math>q_1=q_2</math> ולכן גם <math>r_1=r_2</math>.
	*המספר q נקרא '''מנת''' החלוקה והמספר r נקרא '''שארית''' החלוקה.		*המספר q נקרא '''מנת''' החלוקה והמספר r נקרא '''שארית''' החלוקה.
שורה 338:		שורה 338:
	**<math>ab=(q_an+r_a)(q_bn+r_b)=(q_aq_bn+r_aq_b+q_ar_b)n+r_ar_b</math>		**<math>ab=(q_an+r_a)(q_bn+r_b)=(q_aq_bn+r_aq_b+q_ar_b)n+r_ar_b</math>
	*מסקנה: באותם תנאים, לכל k טבעי מתקיים כי <math>a^k\equiv r_a^k \mod n</math>.		*מסקנה: באותם תנאים, לכל k טבעי מתקיים כי <math>a^k\equiv r_a^k \mod n</math>.


	===המחלק המשותף הגדול ביותר===		===המחלק המשותף הגדול ביותר===

ארז שיינר: ארז שיינר העביר את הדף 89-214 מבנים אלגבריים/תקציר הרצאות ל־מבנים אלגבריים למדעי המחשב - ארז שיינר

2022-04-09T07:54:08Z

ארז שיינר העביר את הדף 89-214 מבנים אלגבריים/תקציר הרצאות ל־מבנים אלגבריים למדעי המחשב - ארז שיינר

→ הגרסה הקודמת	גרסה מ־07:54, 9 באפריל 2022
(אין הבדלים)

→ הגרסה הקודמת		גרסה מ־06:19, 2 בפברואר 2023
שורה 30:		שורה 30:
	*[[מדיה:21ASTestC.pdf\|מבחן מועד ג' תשפ"א]]		*[[מדיה:21ASTestC.pdf\|מבחן מועד ג' תשפ"א]]
	*[[מדיה:22ASTestA.pdf\|מבחן מועד א' תשפ"ב]]		*[[מדיה:22ASTestA.pdf\|מבחן מועד א' תשפ"ב]]
			*[[מדיה:22ASTestB.pdf\|מבחן מועד ב' תשפ"ב]]

→ הגרסה הקודמת		גרסה מ־06:44, 16 באפריל 2026
שורה 184:		שורה 184:
	===סימן של תמורה===		===סימן של תמורה===
	*נביט בחבורת התמורות <math>S_n</math>.		*נביט בחבורת התמורות <math>S_n</math>.
	*עבור <math>f\in S_n</math> נגדיר את הסימן <math>\mathrm{sign}(f):=\Pi_{i~~\neq~~ j}\frac{x_{f(i)}-x_{f(j)}}{x_i-x_j}</math>.		*עבור <math>f\in S_n</math> נגדיר את הסימן <math>\mathrm{sign}(f):=\Pi_{i> j}\frac{x_{f(i)}-x_{f(j)}}{x_i-x_j}</math>.
	*הסימן של תמורה הוא תמיד פלוס או מינוס 1.		*הסימן של תמורה הוא תמיד פלוס או מינוס 1.
	*אם סימן התמורה הוא מינוס אחד אומרים שהיא '''אי-זוגית''' או '''שלילית''', ואם הסימן הוא אחד אומרים שהיא '''זוגית''' או '''חיובית'''.		*אם סימן התמורה הוא מינוס אחד אומרים שהיא '''אי-זוגית''' או '''שלילית''', ואם הסימן הוא אחד אומרים שהיא '''זוגית''' או '''חיובית'''.
שורה 191:		שורה 191:
	*כפליות הסימן: תהיינה שתי תמורות <math>f,g\in S_n</math>, אזי <math>\mathrm{sign}(f\circ g)=\mathrm{sign}(f)\cdot\mathrm{sign}(g)</math>.		*כפליות הסימן: תהיינה שתי תמורות <math>f,g\in S_n</math>, אזי <math>\mathrm{sign}(f\circ g)=\mathrm{sign}(f)\cdot\mathrm{sign}(g)</math>.
	**הוכחה:		**הוכחה:
	**<math>\mathrm{sign}(f\circ g)=\Pi_{i~~\neq~~ j}\frac{x_{f(g(i))}-x_{f(g(j))}}{x_i-x_j}=\Pi_{i~~\neq~~ j}\frac{x_{f(g(i))}-x_{f(g(j))}}{x_{g(i)}-x_{g(j)}}\cdot\frac{x_{g(i)}-x_{g(j)}}{x_i-x_j}</math>		**<math>\mathrm{sign}(f\circ g)=\Pi_{i> j}\frac{x_{f(g(i))}-x_{f(g(j))}}{x_i-x_j}=\Pi_{i> j}\frac{x_{f(g(i))}-x_{f(g(j))}}{x_{g(i)}-x_{g(j)}}\cdot\frac{x_{g(i)}-x_{g(j)}}{x_i-x_j}</math>
	**כיוון שg חח"ע ועל,אוסף הזוגות <math>i~~\neq~~ j</math> שווה לאוסף הזוגות <math>g(i),g(j)</math>, ולכן <math>\Pi_{i~~\neq~~ j}\frac{x_{f(g(i))}-x_{f(g(j))}}{x_{g(i)}-x_{g(j)}}=\mathrm{sign}(f)</math>.		**כיוון שg חח"ע ועל,אוסף הזוגות <math>i> j</math> שווה לאוסף הזוגות <math>g(i),g(j)</math>, ולכן <math>\Pi_{i> j}\frac{x_{f(g(i))}-x_{f(g(j))}}{x_{g(i)}-x_{g(j)}}=\mathrm{sign}(f)</math>.
	**סה"כ קיבלנו <math>\mathrm{sign}(f\circ g)=\mathrm{sign}(f)\cdot\mathrm{sign}(g)</math>.		**סה"כ קיבלנו <math>\mathrm{sign}(f\circ g)=\mathrm{sign}(f)\cdot\mathrm{sign}(g)</math>.


	<videoflash>Lmk0izbQR08</videoflash>		<videoflash>Lmk0izbQR08</videoflash>


	===מחזורים===		===מחזורים===