On 9/9/07, John Cremona <[EMAIL PROTECTED]> wrote:
>
> ...which is more or less what I had done before: it's at
>
> http://www.warwick.ac.uk/staff/J.E.Cremona/mwrank/
>
> (and you may also like to note that from now on my home page is at
>
> http://www.warwick.ac.uk/staff/J.E.Cremona
> )
>
> For
PS the changed files are gpslave.h/cc, parifact.h/cc, marith.cc
On 9/9/07, William Stein <[EMAIL PROTECTED]> wrote:
>
> On 9/9/07, John Cremona <[EMAIL PROTECTED]> wrote:
> > I have added the following functionality to the mwrank package:
> > * an interface to pari's isprime() function which (as
...which is more or less what I had done before: it's at
http://www.warwick.ac.uk/staff/J.E.Cremona/mwrank/
(and you may also like to note that from now on my home page is at
http://www.warwick.ac.uk/staff/J.E.Cremona
)
For the future I guess I need to do "hg push" to somwhere.
John
On 9/9/
On 9/9/07, John Cremona <[EMAIL PROTECTED]> wrote:
> I have added the following functionality to the mwrank package:
> * an interface to pari's isprime() function which (as we confirmed
> recently) really does provide a proof that primes are prime
> * integer factorization using the pari library i
I have added the following functionality to the mwrank package:
* an interface to pari's isprime() function which (as we confirmed
recently) really does provide a proof that primes are prime
* integer factorization using the pari library is now followed by
calling isprime() on the prime factors fo
Here are the remaining timings for Pari vs Magma for computing class
groups.
Executive summary: Magma eventually catches up with Pari and overtakes
it for some computations. Basically Magma doesn't like large
discriminants.
As before, four dots means Magma took too long and I killed it:
Degree,
I *think* this one will be OK. The call to the factoring algorithm is
probably just to look for small factors and for perfect powers. It's
mainly done for efficiency reasons I think.
I noticed this too, but decided it was probably OK (pun intended).
Bill.
On 7 Sep, 20:51, "John Cremona" <[EMAIL
John Cremona wrote:
> It gets worse: (with GP/PARI 2.4.2):
>
> ? default(debug,2)
> %5 = 2
> ? p=nextprime(10^20)
> %6 = 10039
> ? isprime(p)
> *** isprime: Warning: IFAC: untested integer declared prime.
> 507526619771207
> %7 = 1
>
> -- so one call to isprime(), whic
It gets worse: (with GP/PARI 2.4.2):
? default(debug,2)
%5 = 2
? p=nextprime(10^20)
%6 = 10039
? isprime(p)
*** isprime: Warning: IFAC: untested integer declared prime.
507526619771207
%7 = 1
-- so one call to isprime(), which supposedly proves a proof, involves
furthe
The number field code in Pari relies on factoring the discriminant
often using MPQS. In particular if you turn debugging mode on, you get
warnings like this:
*** bnfclassunit: Warning: IFAC: untested integer declared prime.
10762727634633706239259776012492757340083
So basically the num
On 9/7/07, John Cremona <[EMAIL PROTECTED]> wrote:
>
> As a first attempt I was going to add the isprime() test to the
> factors returned and just output a warning if one of them fails. I
> guess that pari-dev would be interested in such examples anyway.
>
> BTW, not sure how I am supposed to pro
As a first attempt I was going to add the isprime() test to the
factors returned and just output a warning if one of them fails. I
guess that pari-dev would be interested in such examples anyway.
BTW, not sure how I am supposed to provide patches to mwrank source
code except by emailing the chan
William, the trac ticket should read > 10^15, not < 10^15.
Bill.
On 7 Sep, 18:23, "William Stein" <[EMAIL PROTECTED]> wrote:
> On 9/7/07, John Cremona <[EMAIL PROTECTED]> wrote:
>
> > On 9/7/07, Bill Hart <[EMAIL PROTECTED]> wrote:
> > > Are there other algorithms available in SAGE from Pari tha
On 7 Sep, 08:55, "John Cremona" <[EMAIL PROTECTED]> wrote:
> The pari manual says (about factor(x)):
>
> If $x$ is of type integer or rational, the factors are \var{pseudoprimes}
> (see \kbd{ispseudoprime}), and in general not rigorously proven primes. In
> fact, any factor which is $\leq 10^{15
On 9/7/07, John Cremona <[EMAIL PROTECTED]> wrote:
> On 9/7/07, Bill Hart <[EMAIL PROTECTED]> wrote:
> > Are there other algorithms available in SAGE from Pari that rely on
> > conjectures? This would include the stuff for totally real fields that
> > relies on the Stark conjectures.
>
> mwrank us
On 9/7/07, Bill Hart <[EMAIL PROTECTED]> wrote:
>
>
> Are there other algorithms available in SAGE from Pari that rely on
> conjectures? This would include the stuff for totally real fields that
> relies on the Stark conjectures.
mwrank uses the pari library for factorization of integers, so the
Oh, I also want to test whether Magma is able to benefit from knowing
that a field is a compositum, totally real or abelian, etc, when
computing class groups. If so, this would constitute functionality
SAGE may want to emulate.
Bill.
--~--~-~--~~~---~--~~
To post
Here is a (probably not comprehensive list) of functions in NTL which
allow or use probabilistic strategies with a probability of incorrect
results:
GF2EX::ProbMinPolyMod
GF2EXFactoring::ProbIrredTest
lzz_pX::ProbMinPolyMod
lzz_pXFactoring::ProbIrredTest
lzz_pXFactoring::ProbComputeDegree
lzz_pEX
On 7 Sep, 02:21, "William Stein" <[EMAIL PROTECTED]> wrote:
> SAGE uses PARI. PARI claims to prove primality under no hypothesis
> "using a combination of algorithms" including Pocklington-Lehmer
> and APRCL.
OK. I certainly didn't know of this. That invalidates what I say about
Pari below. B
On 7 Sep, 01:45, "William Stein" <[EMAIL PROTECTED]> wrote:
> On 9/6/07, Bill Hart <[EMAIL PROTECTED]> wrote:
>
> > The question is, which algorithm does SAGE currently use?
>
> For class groups?
Yes.
> If so, it uses pari, then calls the
> bnfcertify command after doing the computation.
OK
On 9/6/07, Bill Hart <[EMAIL PROTECTED]> wrote:
> While we are at it we should determine the default algorithm which
> SAGE uses for primality checking. If GMP is used for this then it is
> not guaranteed to only pass primes. It simply does a Fermat test and
> then a certain number of rounds of Mi
While we are at it we should determine the default algorithm which
SAGE uses for primality checking. If GMP is used for this then it is
not guaranteed to only pass primes. It simply does a Fermat test and
then a certain number of rounds of Miller-Rabin. Usually to make this
practical GRH is assume
On 9/6/07, Bill Hart <[EMAIL PROTECTED]> wrote:
> The question is, which algorithm does SAGE currently use?
For class groups? If so, it uses pari, then calls the
bnfcertify command after doing the computation.
> Does it
> really provide a proven result?
Assuming pari works correctly.
> Is it
The question is, which algorithm does SAGE currently use? Does it
really provide a proven result? Is it proven to terminate? Can it
provide a certificate that I can check in less time than doing the
computation again? How can I be sure the result is valid?
Anyhow, whatever algorithm or level of r
On 9/6/07, Jaap Spies <[EMAIL PROTECTED]> wrote:
>
> John Cremona wrote:
> > I agree with Nils!
> >
>
> +1
>
+1. OK.
However, I've also added this function to make it really easy to
turn off proof=True globally for just number field stuff:
sage: number_field_proof?
Set or get the globa
John Cremona wrote:
> I agree with Nils!
>
+1
Jaap
> John
>
> On 9/6/07, Nils Bruin <[EMAIL PROTECTED]> wrote:
>> I would be very disappointed if this approach would be taken. Sure, it
>> has to be straightforward and convenient to choose the level of rigour
>> desired in class group computat
I agree with Nils!
John
On 9/6/07, Nils Bruin <[EMAIL PROTECTED]> wrote:
>
> I would be very disappointed if this approach would be taken. Sure, it
> has to be straightforward and convenient to choose the level of rigour
> desired in class group computations, but by default results should be
> u
I would be very disappointed if this approach would be taken. Sure, it
has to be straightforward and convenient to choose the level of rigour
desired in class group computations, but by default results should be
unconditional. It would be a real shame if SAGE, which tries to up the
level of trustw
Yes. Who would have expected the existence of a faster
generic algorithm to compute the order of an element in a group.
Michel
On Sep 6, 1:50 pm, Bill Hart <[EMAIL PROTECTED]> wrote:
> But WOW, what an amazing thesis!! I think you sent this one to me
> before, yes? But this is the first time I
Computing class groups in the imaginary quadratic case is a very
special case. For one thing generically they are not 1!! But also one
can use a large variety of methods, including modular forms. We could
probably use fast polynomial arithmetic in FLINT to do this.
Bill.
On 6 Sep, 12:39, David H
But WOW, what an amazing thesis!! I think you sent this one to me
before, yes? But this is the first time I ever looked at it. This guy
has an amazing result.
Bill.
On 6 Sep, 12:46, Bill Hart <[EMAIL PROTECTED]> wrote:
> Computing class groups in the imaginary quadratic case is a very
> special
Hi guys, sorry to butt in here since I know nothing about computing
class groups, but I just wanted to mention a paragraph in the
introduction to Andrew Sutherland's PhD recent thesis:
"We apply these results to compute the ideal class groups of
imaginary quadratic number fields, a standard
On 9/5/07, Bill Hart <[EMAIL PROTECTED]> wrote:
> Are you asking me? I'm not even sure I understand all the different
> options Magma offers yet!!
>
> Basically I don't see any problem with doing the computation the way
> Pari does it, whatever that equates to in Magma.
I'm specifically asking yo
Are you asking me? I'm not even sure I understand all the different
options Magma offers yet!!
Basically I don't see any problem with doing the computation the way
Pari does it, whatever that equates to in Magma.
*IF* I understand it correctly, from Magma's point of view, Pari uses
the bound Bac
Degree 5 class group timings Pari vs Magma:
5, 5, 1000 : 23-40s 22-31s
x^5 + 816*x^4 + 515*x^3 + 551*x^2 - 594*x - 475 : 3.21s 67.9s
x^5 + 210*x^4 + 1017*x^3 + 763*x^2 - 701*x + 672 : 0.469s 1.57s
x^5 - 832*x^4 + 452*x^3 + 684*x^2 + 818*x + 67 : 3.87s 70.8s
x^5 - 2403*x^4 + 7461*x^3 + 1192*x^2 +
On 9/5/07, Bill Hart <[EMAIL PROTECTED]> wrote:
>
> Degree 4:
>
> 4, 5, 1000 : 10s 10s
> 4, 10, 100 : 20-30s 21-30s
> x^4 - 19668*x^3 + 17560*x^2 + 26384*x + 30412 : 7.89s
> x^4 - 956*x^3 - 7384*x^2 + 2639*x - 17854 : 1.01s 100s
> x^4 - 1059*x^3 + 30230*x^2 + 10713*x + 25155 : 0.521s 13.5s
>
Degree 4:
4, 5, 1000 : 10s 10s
4, 10, 100 : 20-30s 21-30s
x^4 - 19668*x^3 + 17560*x^2 + 26384*x + 30412 : 7.89s
x^4 - 956*x^3 - 7384*x^2 + 2639*x - 17854 : 1.01s 100s
x^4 - 1059*x^3 + 30230*x^2 + 10713*x + 25155 : 0.521s 13.5s
x^4 + 27001*x^3 + 7255*x^2 + 16695*x + 23797 : 16.3s
x^4 - 2
On the other hand the times for cubic fields are not changed by
calling SetClassGroupBounds("PARI");
This tells me that Magma likely uses BachBound(K)/40 for quadratic
fields too. There would be nothing wrong with this since Pari used to
do this itself but it slowed Pari down for large discrimina
38 matches
Mail list logo
