Computer Algebra (MA3101)
Vorlesung |
Lectures: | Prof. Dr. G. Kemper |
---|---|
Tutorial management: | Dipl.-Math V. Ghiglione |
Tutorials: | Dipl.-Math V. Ghiglione |
News | Schedule | Lecture Notes | Problem Sheets | Literature | Exam | FAQ |
News
- July, 27th 2015: Here you find the matrikel numbers of the students that achieved the Notenbonus. Please contact the Tutor if you have any question concerning this.
- July, 21st 2015: The second try of the exam will take place on September 23rd.
- July, 13th 2015: Sheet 11 has been uploaded. It is a bonus sheet, if handed in, it counts for the noten bonus. The total numbers of exercises that will considered to check if the bonus applies is 39 (sheets 1--10). Please hand it in by Friday 17 at 12:00 if you would like to have a feedback by Thursday 23, or hand it in by Monday 20 at 12:00 otherwise.
- July, 1st 2015: The exam for the course will be held orally on the dates July 29 and July 30, 2015. If you are not planning to take the exam, please inform us (by email or by cancelling your registration) before July 14. The schedule of the exam will be published after July 14.
- June, 25th 2015: Sheet 8 has been updated, see below.
- June, 18th 2015: A link to the lecture notes typed by Lars Wüstrich has been published, see below.
- June, 15th 2015: Suggested solutions to sheets 1--5 have been uploaded.
- June, 10th 2015: Sheet 6 has been updated. Please check the details below.
- June, 8th 2015: The dates of the oral exam (in case this option will apply) changed to 29th and 30th July 2015. See dedicated section below.
- May, 21st 2015: As Monday 25th is holiday as well as Tuesday 26th, you may hand in Sheet 4 by Wednesday May 27th at 10am. Exercise 2.c.(iii) was crossed out.
- May, 12th 2015: Sheet 4 is uploaded in case you want to work ahead on it, as the exercises' topics have been already covered in the lecture. We will work on it during next tutorial, on May 21st.
- May, 4th 2015: Exam date(s) are now fixed. See dedicated section below.
- April, 8th 2015: The first class will take place on Monday, April 13th, 2015 in room MI HS 3 at 12:00. We will start by giving you some details on tutorials and organization. Registration for the tutorials will start after the first lecture. Tutorials are scheduled on Thursdays from 12:00 to 14:00. The first tutorial will take place on April, 23rd 2015.
Schedule
Lectures
Day | Time | Room | Lecturer |
---|---|---|---|
Mon | 12:00-13:30 | MI HS3 | G. Kemper |
Thu | 08:30-10:00 | MI HS3 | G. Kemper |
Tutorial Classes
Day | Time | Room | Tutor |
---|---|---|---|
Thu | 12:15-14:00 | MI 02.09.014 | V. Ghiglione |
Office Hours
Person | Day | Time | Room | Not in the office |
---|---|---|---|---|
G.Kemper | Tue | 13:00-14:00 | MI 02.10.57 | |
V. Ghiglione | Wed | 14:00-15:00 | MI 02.04.36 | 22.04, 22.07 |
Lecture Notes
Lars Wüstrich is writing up the notes from the lectures, and has kindly given us permission to publish the link to the current version. Lecture Notes written by Lars Wüstrich ^{}Problem Sheets
Sheet | Topics | Comments |
---|---|---|
Sheet 1 | Asymptotic behaviour, KaratsubaŽs Algorithm, DFT and FFT | |
Sheet 2 | Kronecker Substitution, Squaring vs Multiplying, Generalized Euclidean Algorithm, FFT | Ex.3(a) removed, Typo in ex.4 corrected (R set of polynomials of degree <2^{k-1}) |
Sheet 3 | Euclidean Algorithm in Gaussian integers, Residue computations, Carmichael numbers, Fermat primality test | Hand-in by May 18th |
Sheet 4 | Miller-Rabin Test, Fermat Numbers, A primality criterion, AKS Test | Hand-in by May 27th, 10am. Exercise 2.c.(iii) was crossed out. |
Sheet 5 | RSA, Factorization with known private key, Low-exponent Attack | Hand-in by June 8th. Changed number in encrypted text of exercise 1: 0597 instead of 1778 |
Sheet 6 | Pollard's rho algorithm for DLP, Pollard's rho algorithm, Pollard's p-1 algorithm | In ex 3, " running time of the algorithm" was replaced with "number of runs through the loop in the algorithm" |
Sheet 7 | Quadratic Sieve, Strassen Multiplication, Comparison of running times, LU and LUP decomposition | |
Sheet 8 | Ideals, Affine Varieties and ideals, Cartesian and Parametric Form | Ex.2(c) was corrected to : x is not zero-divisor ... In ex.3(b) "=V(IJ)=" has been added |
Sheet 9 | Monomial Orderings, Monomial orderings with matrices, Ascending chain condition, Noetherian rings | |
Sheet 10 | Normal Form, Superfluous Pairs, Reduced GB, Systems of polynomial equations | |
Sheet 11 | Coloring Graphs, Formal Power Series, Hilbert Function, Zariski Topology | This is a Bonus Sheet: you may hand it in by Monday 20th, to have a feedback by Monday 27th, or hand it in by Friday 17 at 12 to have a feedback by Thursday 23 |
Suggested Solutions
Sheet 1, Sheet 2, Sheet 3, Sheet 4, Sheet 5, Sheet 6, Sheet 7, Sheet 8, Sheet 9, Sheet 10, Sheet 11Homeworks and Noten Bonus
- Every Monday a new sheet is uploaded online.
- Hand in your solution in groups of 2-3 people by the following Monday at 12, either putting it in the mail box in the basement or sending it via email to the Tutor.
- The homeworks will be returned on Thursday in the Tutorial (and left in a folder in the closet at the beginning of Finger 02.04 afterwards).
- By the end of the sememster, those who had at least 70% of the exercises (all together) evaluated with "reasonable attempt" will get a bonus of 0.3 to the exam grade (not passing grades cannot benefit from the bonus).
- Here you can download the cover sheet that you can use for all your homeworks.
Exam
The exam will be held orally and will take place on July 29th and July 30th. If you are not planning to take the exam, please inform us (by email or by cancelling your registration) before July 14. The schedule of the exam will be published after July 14. Wiederholungsklausur The second try of the exam will take place on September 23rd.Literature
- J. von zur Gathen, J. Gerhard: Modern Computer Algebra, Cambridge University Press, Cambridge, 1999.
- C. Karpfinger, H. Kiechle: Kryptologie: Algebraische Methoden und Algorithmen, Vieweg+Teubner, 2009.
FAQ
How can I get Maple?The computer algebra system Maple will be used in the tutorials and for homework. Students have access to Maple in the Rechnerhalle. Is it possible also to make use of the remote access to the Rechnerhalle computers. Where can I find a Maple Manual?
Tutorials and explanations can be found at the page http://www.maplesoft.com/support/help/