Hi folks, I've started working on a new C library called "zn_poly", which does polynomial arithmetic in (Z/nZ)[x], where n fits into an unsigned long. Similar to NTL's zz_pX class. This might eventually be part of FLINT, but for now it's a separate project.
I am maintaining a website for zn_poly at http://math.harvard.edu/~dmharvey/zn_poly/ I have made an spkg for sage-2.9, you can get it from http://math.harvard.edu/~dmharvey/zn_poly/releases/zn_poly-0.4.1.spkg I don't know if this will build on all sage-supported systems yet. So far I have successfully built on: * sage.math (AMD opteron, debian linux) * bsd (a xeon I think?) * my laptop: core 2 duo, mac OS 10.4.10 * my desktop: ppc G5, mac OS 10.4.10 * my very old laptop: ppc G3, mac OS 10.3.9 (zn_poly, but not the spkg) I'd really appreciate people trying this out on various systems and reporting back what happens. As an application, I rewrote my "frobenius" program, which is currently included in Sage via sage.schemes.hyperelliptic_curves.frobenius.frobenius. This program computes the characteristic polynomial of frobenius (i.e. the zeta function) for a hyperelliptic curve over GF(p), where p is relatively large. Here is a patch which upgrades to the new version: http://sage.math.washington.edu/home/dmharvey/patches/hypellfrob.hg The algorithm depends heavily on polynomial arithmetic, often for a small (word-sized) modulus. The old version used NTL for the polynomial arithmetic (either ZZ_pX or zz_pX). The new version attempts to use zn_poly arithmetic where possible. Below are some example timings for the new version (on sage.math). It incorporates some algorithmic improvements too, but a lot of the speedup is due to zn_poly vs NTL. genus 2 (compute charpoly mod p) p = 2^16 + 1: old = 0.068s, new = 0.008s p = 2^20 + 7: old = 0.288s, new = 0.044s p = 2^24 + 43: old = 1.244s, new = 0.324s p = 2^28 + 3: old = 5.63s, new = 2.952s p = 2^32 + 15: old = 29.0s, new = 21.6s genus 3 (compute charpoly mod p) p = 2^16 + 1: old = 0.136s, new = 0.020s p = 2^20 + 7: old = 0.580s, new = 0.092s p = 2^24 + 43: old = 2.548s, new = 0.648s p = 2^28 + 3: old = 11.4s, new = 5.9s p = 2^32 + 15: old = 58.2s, new = 43.3s genus 4 (compute charpoly mod p^2) p = 2^16 + 1: old = 0.61s, new = 0.16s p = 2^20 + 7: old = 5.23s, new = 0.92s p = 2^24 + 43: old = 25.7s, new = 20.3s p = 2^28 + 3: old = 233s, new = 111s p = 2^32 + 15: old = 1246s, new = 1313s Hmmmm.... that last one ain't so great. That's because zn_poly excels at small-to-medium polynomials, but isn't so good for large polynomials (yet!). david --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
