Sidan uppdaterades 14 december

Kursansvarig:            Johan Berglind
                                     tel:  031 - 772 3584
                                     e-mail:  johan.berglind@chalmers.se


Kurslitteratur:         James Strayer, Elementary Number Theory

                             

Examination:           Inlämningsuppgifter kan ge bonuspoäng på tentamen i augusti. Reglerna anges i dokumentet.

Kursens omfattning:   Kursen täcker strängt taget kapitel 1 till och med 6.3 i kursboken, samt avsnitt 8.2 och Appendix 1.
                                      Därtill kommer några tillämpningar, bland annat om kryptografi. På grund av tidsbrist utgår avsnitt 3.3 samt 3.6

                               Extra material:        Kappsäckskrypto     Faktoriseringsalgoritmer     Slantsingling
                                                                ElGamal kryptering

Övningstentamen:   Det finns gott om gamla tentamina på hemsidan från 2005. Men eftersom kursens innehåll och inriktning är något förnyad
                                  finns det även tillgång till två färska övningstentamina:                                    Första övningstentamen                  Andra övningstentamen            
                                                                                                                                                                                                                    Lösningar till andra övntent
Observera om Andra övningstentamen: i slutet av uppgift 5 skall det stå a(j)>=2^(j-1)

Tentamen aug07                          Lösningar till Tentamen aug07
Tentamen sept 07                              Lösningar till Tentamen sept 07

***************************************************  OM TENTAMEN  ****************************************************************************

Angående tentamen: det enda tillåtna hjälpmedlet är en  godkänd räknedosa

 Tentamen 20 aug består av 8 uppgifter om sammanlagt 25 poäng. Det finns ingen tydligt uppdelning i problem och teoriuppgifter; det förekommer inga frågor av typen "formulera och bevisa satsen ... ". Däremot finns det all anledning att vänta sig uppgifter som är nära relaterade till någon känd sats i kursen, och vars lösning kräver att man har förstått de väsentliga delarna av beviset för denna sats. Glöm inte att studera det extra materialet.

**************************************************************************************************************************************************


Preliminär Veckoplanering:

Vecka 24; 11 - 15 juni

dag	Föreläsning	Demonstrationsuppgifter	Övningsuppgifter
tisdag	Kursen introduceras. Vi pratar om delbarhet, primtal och största gemensamma delare. Vad det innebär att två tal är relativt prima är värt att lägga på minnet.		1.1    1, 2, 4, 5, 7, 9, 10, 12. 1.2    16, 21b, 23 - 26, 28, 30. 1.3    32bc, 33d, 34de, 36, 38, 41, 43.
onsdag	Vi börjar med en utflykt till Appendix A och matematisk induktion. Induktion är inget centralt begrepp i kursen, men det används då och då i bevisen och hör på något sätt till allmänbildningen inom talteorin. Därefter återvänder vi till kapitel 1 med Euklides algoritm och Aritmetikens fundamentalsats, och bekantar oss med en gammal och inte alltid effektiv faktoriseringsalgoritm.	1.3    39, 42. 1.5    61d, 63a, 71.	1.4    54ace, 55. 1.5    59bdg, 61c, 64, 69, 70, 72, 78, 83.
torsdag	I kapitel 2 introduceras kongruenser och här kan vi säga att kursen börjar på allvar. Mycket av det som kommer att behandlas försigår i så kallade restsystem, så begreppet är väsentligt. Veckan avslutas med Kinesiska restsatsen.	2.1     5b, 14. 2.2     29b. 2.3     33c, 34c.	2.1    1bcd, 2ad, 3b, 5a, 6b, 8, 9, 13, 17, 23, 26. 2.2    28ace, 29a-e. 2.3    33bd, 34ab, 35, 36.

Vecka 25; 18 - 22 juni

dag	Föreläsning	Demonstrationsuppgifter	Övningsuppgifter
tisdag	Vi arbetar vidare med kongruenser och stöter på tre viktiga satser: Wilsons, Fermats lilla samt Eulers. Begreppet pseudoprimtal dyker också upp här.	2.4     42d. 2.5     51d, 54b.	2.4   42ace, 44, 45, 47bc, 48. 2.5   51ac, 52, 53a, 54a, 56b, 57a, 59. 2.6   68ac, 69acd, 71, 76.
onsdag	Nu vet vi tillräckligt för att uppskatta två krypteringsmetoder, Kappsäckskrypto och RSA-metoden, samt två moderna faktoriseringsalgoritmer: Pollard rho och Pollard p-1.	2.4     47a, 2.5     58b. 2.6     68b, 70a.
torsdag	Vi repeterar kapitel 2 och introducerar kapitel 3 som handlar om Eulers phi-funktion och ett par släktingar till denna.	3.2     10fg, 13ef	3.1    3, 4, 5bde, 6. 3.2    9, 10abch, 13ac, 14, 15, 17.

Vecka 26; 25 - 29 juni

dag	Föreläsning	Demonstrationsuppgifter	Övningsuppgifter
tisdag	Vi avslutar kapitel 3 som läses översiktligt. Vi koncentrerar oss på att klassificera perfekta tal och lämnar Möbius inversionsformel till självstudier. På så sätt hinner vi presentera kvadratiska residyer från kapitel 4.	3.3     31c, 33. 3.4     45. 4.1     1c, 8.	3.3   30abd, 31ad, 32, 33, 35. 3.4    42abc, 44, 46. 3.5    57.
onsdag	Kvadratiska residyer är klassisk talteori och inte helt trivial sådan. Legendre-symbolen införs och flera viktiga delresultat inför morgondagen huvudsats gås igenom. Nyttan med denna teori framgår när vi lär oss singla slant - elektroniskt.	4.2     14f, 17, 21, 26.	4.1    1b, 3, 5a, 6, 9. 4.2    12, 13, 14ade, 15, 16, 18, 20, 25.
torsdag	Så gott som hela dagen går åt till satsen om kvadratisk reciprocitet.	4.3     28b, 36b.	4.3    28ace, 30, 32 - 35.

Vecka 32; 6 - 10 augusti

dag	Föreläsning	Demonstrationsuppgifter	Övningsuppgifter
tisdag	Kapitel 5 handlar egentligen om så kallade diskreta logaritmer. För att kunna använda sådana behöver man primitiva rötter, dvs tal som så att säga genererar alla reducerade rester modulo något givet tal. Som ett första steg visar vi att alla primtal har primitiva rötter.	5.1    1b, 3c, 5a. 5.2    11c.	5.1    1ac, 2a, 3ab, 4, 7, 8. 5.2    10c, 11ab.
onsdag	Vi fortsätter och reder ut exakt när det finns primitiva rötter.	5.2    12, 14ab. 5.3    23cd.	5.2    13, 15, 16, 18. 5.3    23ab, 27, 28.
torsdag	ElGamal kryptering är en tillämpning på kapitel 5. Om detta står inte mycket i boken, men det finns en länk bland extra materialet ovan. I mån av tid skall vi också diskutera något om primtalstester.	5.4    29b, 30f, 32c, 38.	5.4    29a, 30ae, 31, 32ab, 34b, 35, 36.

Vecka 33; 13 - 17 augusti

dag	Föreläsning	Demonstrationsuppgifter	Övningsuppgifter
tisdag	Diofantiska ekvationer i kapitel 6 läser vi översiktligt. Vi borde hinna med de tre första avsnitten som är ganska korta.	6.1    2b. 6.2    11cd. 6.3    14c, 16d.	6.1    2ad, 3, 6b, 8a. 6.2    11abe. 6.3    14ab, 16ab.
onsdag	Repetition
torsdag	Repetition