|
Size: 2692
Comment:
|
Size: 3194
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 5: | Line 5: |
| == Part of my Thesis == * My thesis deals with algebraic attacks on block ciphers namely the Courtois Toy Cipher. So I will implement/have implemented several algebraic attack algorithms like XL,XSL,F4 and DR. Though those might not be of general interest. == Other stuff I'm working on == * Real cputime() including subprocesses. Either the host OSes are kind enough to provide us with the needed information or we need to query every process for its cputime(). Most CASes seem to offer this information, if they don't: Query the OS. * Cputime class/function which wraps all the cputime() calls for all the subprocesses for convenience. So only one '''cputime(all=True)''' call would be sufficient. |
== Stuff I'm working on == * ntl.GF2E & ntl.ZZpX wrapping for finite fields * Possible: Specialized MPolynomialGF2 class * Possible: Improve F4 implementation or start over in cooperation with some of the other developers working on F4 right now |
| Line 12: | Line 16: |
| Line 13: | Line 18: |
| * Allow %prun and hotshot to profile pyrex code. * [http://www-id.imag.fr/Logiciels/givaro/ Givaro] integration. This significantly improves finite field arithmetic (more than ten times) and everything relying on it in SAGE. Try it: '''k = linbox.GFq(2^8,repr="poly")''' * Extremely fast sparse (and dense) linear algebra. Actually I only care about echelon form calculation. We are debating if [http://www.linalg.org LinBox] is a good choice for this. Matrices involved in algebraic attacks are often very sparse and there is no need to have my machine go down because e.g., NTL allocates many zeros (i.e., NTL only knows dense matrices). * Parallel sparse linear algebra to utilize all 16 cores at sage.math.washington.edu at once. :) It's either to hard for me (if there is no library) or simple as it would be just another library to expose. |
* Parallel sparse linear algebra to utilize all 16 cores at sage.math.washington.edu at once. :) It's either too hard for me (if there is no library) or simple as it would be just another library to expose. |
| Line 18: | Line 22: |
| Line 19: | Line 24: |
| * Implement or wrap the [http://eprint.iacr.org/2006/251.pdf "Method of Four Russians"] for row reducing resp. inverting a dense boolean matrix | |
| Line 21: | Line 25: |
| = Other stuff = I'm a computer science grad student from Bremen, Germany with a strong interest in cryptanalysis, right now mainly algebraic attacks on block ciphers. I maintain a blog at http://www.informatik.uni-bremen.de/~malb/blog.php . |
* NTL wrapper makeover (more SAGEish, avoid function calls, avoid news, deletes) == Done == * Speed up MPolynomials by linking to Singular (this is going to be an exciting experience on its own) or CoCoALib (as of version 2.5.1) * My thesis deals with algebraic attacks on block ciphers namely the Courtois Toy Cipher. So I implemented several algebraic attack algorithms like XL, F4, and DR and a slightly optimized MPolynomial over GF(2) class. Though those might not be of general interest. I will push some of that stuff upstream. * Givaro is going to be in SAGE 1.5 * Cputime class/function which wraps all the cputime() calls for all the subprocesses for convenience. So only one '''cputime(all=True)''' call would be sufficient. (I extended David Harvey's Profiler class for this) * Consider this example: {{{#!python sage: R1 = PolynomialRing(GF(2**8),2) sage: R2 = PolynomialRing(GF(2**8),2000) sage: x1=R1.gen() sage: y1=R1.gen(1) sage: x2=R2.gen() sage: y2=R2.gen(1) sage: time for i in range(1000): _ =x2*y2 CPU times: user 1.58 s, sys: 0.03 s, total: 1.61 s Wall time: 1.63 #ring with 2000 variables sage: time for i in range(1000): _ =x1*y1 CPU times: user 0.21 s, sys: 0.03 s, total: 0.24 s Wall time: 0.24 #ring with two variables }}} This is due to the way multivariate polynomials in SAGE are represented. I want to come up with a more sparse representation which does not add zero to zero 1998 times in the second example. (I rewrote the polynomial representation to use dicts of dicts which map indices to exponents e.g., {{1:2}:3} represents 3*y^2 if y is the second variable in the ring.) == Other stuff == I studied computer science in Bremen, Germany. I am applying to several grad schools right now to find a nice university to earn a PhD. I have a a strong interest in cryptanalysis, right now mainly algebraic attacks on block ciphers. I maintain a blog at http://www.informatik.uni-bremen.de/~malb/blog.php . |
Martin Albrecht's (malb) SAGE projects
Stuff I'm working on
ntl.GF2E & ntl.ZZpX wrapping for finite fields
- Possible: Specialized MPolynomialGF2 class
- Possible: Improve F4 implementation or start over in cooperation with some of the other developers working on F4 right now
- Memory consumption analogous to cputime(). This is tricky because some grep on top et al. doesn't provide the necessary information. E.g. Python never ever frees memory while running, and we also might count shared libraries several times this way.
- Memory profiling similar to %prun or hotshot. The memory profiler would provide hints which part consumes the most memory during a calculation.
Parallel sparse linear algebra to utilize all 16 cores at sage.math.washington.edu at once.
It's either too hard for me (if there is no library) or simple as it would be just another library to expose. [http://article.gmane.org/gmane.comp.mathematics.sage.general/193/ SAGEBot] is not dead yet.
[http://eprint.iacr.org/2006/224.pdf Generalizations of the Karatsuba Algorithm for Efficient Implementations]
- NTL wrapper makeover (more SAGEish, avoid function calls, avoid news, deletes)
Done
- Speed up MPolynomials by linking to Singular (this is going to be an exciting experience on its own) or CoCoALib (as of version 2.5.1)
- My thesis deals with algebraic attacks on block ciphers namely the Courtois Toy Cipher. So I implemented several algebraic attack algorithms like XL, F4, and DR and a slightly optimized MPolynomial over GF(2) class. Though those might not be of general interest. I will push some of that stuff upstream.
- Givaro is going to be in SAGE 1.5
Cputime class/function which wraps all the cputime() calls for all the subprocesses for convenience. So only one cputime(all=True) call would be sufficient. (I extended David Harvey's Profiler class for this)
Consider this example:
This is due to the way multivariate polynomials in SAGE are represented. I want to come up with a more sparse representation which does not add zero to zero 1998 times in the second example. (I rewrote the polynomial representation to use dicts of dicts which map indices to exponents e.g., {{1:2}:3} represents 3*y^2 if y is the second variable in the ring.)1 sage: R1 = PolynomialRing(GF(2**8),2) 2 sage: R2 = PolynomialRing(GF(2**8),2000) 3 sage: x1=R1.gen() 4 sage: y1=R1.gen(1) 5 sage: x2=R2.gen() 6 sage: y2=R2.gen(1) 7 sage: time for i in range(1000): _ =x2*y2 8 CPU times: user 1.58 s, sys: 0.03 s, total: 1.61 s 9 Wall time: 1.63 #ring with 2000 variables 10 sage: time for i in range(1000): _ =x1*y1 11 CPU times: user 0.21 s, sys: 0.03 s, total: 0.24 s 12 Wall time: 0.24 #ring with two variables
Other stuff
I studied computer science in Bremen, Germany. I am applying to several grad schools right now to find a nice university to earn a PhD. I have a a strong interest in cryptanalysis, right now mainly algebraic attacks on block ciphers. I maintain a blog at http://www.informatik.uni-bremen.de/~malb/blog.php .