Eratosthenes Sieve

I have done some work on Eratosthenes sieve and in that connection made a few implementations. Here is a C implementation and a Java implementation. Currently(12-10-2012) the Java implementation is more efficient than the C implementation! I have also implemented a parallel version download with which I in connection wrote the following paper download (pdf). You need a distribution of the BSP library (and linux), on my laptop I use MulticoreBSP for C developed by Albert-Jan Yzelmann http://www.multicorebsp.com/.

Tropical Varieties

Consider the ordinary real numbers R and the usual operations +,* which makes R into a ring. Instead of going further, consider instead the following operations a +' b = min{a,b} and a *' b = a + b i.e. addition is taking minimum and multiplication is doing normal addition. One can then show that +' and *' define a semigroup on R union with infinity. The infinity element is the neutral element for the addition +'. This is the foundation of Tropical geometry. The following project, written in connection with a course on algebra & polyhedral geometry, gives a gentle introduction to tropical varieties and some computational aspects of these. Download (pdf).

Rational monic polynomials

Following write-up is a consequence of a challenge given by Niels Lauritzen in the course advanced algebra. The theorem says that if the product, of (a priori) two monic rational polynomials, has only integer coefficients, then the two polynomial factors must actually be integer polynomials. Note that the write-up is in Danish. Download(pdf).

Factoring and seiving

Everybody (at least a mathematician) probably knows the sieve of Erastothenes; let A be the integers from 2 to some limit n then

do{take next uncrossed number in A and cross out all strict multiples of this number}
while(next uncrossed number is smaller than n).

This is (maybe) the best known sieve out there, but there exists several other usable sieves e.g. to find smooth numbers. This kind of sieving is used in a factorization method known as the quadratic sieve factorization method. The basic fact that this algorithm uses is work by Fermat; if n is odd there exists a,b such that n=a^2-b^2. In the following project, which was written in connection with a course on number theory, I investigate the quadratic sieving factorization algorithm and the theory behind some of the concepts used. Download(pdf).