Opened 5 years ago
Closed 5 years ago
#19929 closed enhancement (duplicate)
GF(16) (without explicit variable name)
Reported by:  ncohen  Owned by:  

Priority:  major  Milestone:  sageduplicate/invalid/wontfix 
Component:  number fields  Keywords:  
Cc:  cremona, dimpase, vdelecroix  Merged in:  
Authors:  Nathann Cohen  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  public/19929 (Commits, GitHub, GitLab)  Commit:  e0259bf16f00e08b86e5bb743cf1df76b578e1aa 
Dependencies:  Stopgaps: 
Description (last modified by )
This branch is related to the following sagedevel conversation:
https://groups.google.com/d/topic/sagedevel/MeuOjHf3vCw/discussion
The default name picked here is 'a'. Indeed, the default name 'conway' proposed on the conversation did not seem adapted, as the default behaviour of the constructor is 'conway=False'. I frankly admit that I do not understand what is the expected behaviour of 'conway=False', but I thought that setting a default name of 'conway' when a field is created with 'conway=False' sounded like a bad idea.
I did not change the default value of 'name' in the function's definition for it would disable an apparently desired behaviour of 'prefix' (when 'name' is undefined). I don't understand why we need all of 'name/names/prefix' in the same function, but I learnt in the past that asking questions like that only brought me pain and suffering.
Nathann
Change History (18)
comment:1 Changed 5 years ago by
 Description modified (diff)
comment:2 Changed 5 years ago by
 Branch set to public/19929
 Cc cremona dimpase vdelecroix added
 Commit set to f96f09f848e3b9877aa50c4d4c26557e2181a9fd
 Status changed from new to needs_review
comment:3 followup: ↓ 4 Changed 5 years ago by
I would argue for #17569 over having 'a' be the default variable name. Nathann, do you object to the solution proposed there?
comment:4 in reply to: ↑ 3 ; followup: ↓ 5 Changed 5 years ago by
I would argue for #17569 over having 'a' be the default variable name. Nathann, do you object to the solution proposed there?
If you see how to implement what is described at #17569 by something like next week and have it in needs_review by then, I don't have *any* objection. I just want it to work.
If you want me to close a ticket that implements a ready solution to a problem in exchange for a 13 months old ticket that still does not contain any code, then of course I object.
To me, a ticket without code just does not exist. It is a thought in somebody's head, and this somebody often has forgotten it. I don't close tickets because of that.
Nathann
comment:5 in reply to: ↑ 4 Changed 5 years ago by
Replying to ncohen:
I would argue for #17569 over having 'a' be the default variable name. Nathann, do you object to the solution proposed there?
If you see how to implement what is described at #17569 by something like next week and have it in needs_review by then, I don't have *any* objection. I just want it to work.
Understandable, since that ticket was based on a conversation from a year ago. I'll work on it and get back to you by next week.
comment:6 Changed 5 years ago by
Thanks,
Nathann
comment:7 followups: ↓ 8 ↓ 9 Changed 5 years ago by
Some points:
 Background:
conway=True
would be absurd, because computing the conway polynomial representation of a finite field is *incredibly* hard in general.
 Using 'a' (or 'x') everywhere as the default is not so good; I did exactly that with number fields back in 20042006 and it caused confusion and people hated it. You easily end up with several different things that all print the same way (magma has this problem now, where everything prints as $.1; but in Magma, you can change the name after creation, as they have no coercion model or reason for not allowing changing the names). I would recommend using something like
"a%s"%(p^n)
or"a_%s_%s"%(p,n)
or"a%s_%s"%(p,n)
, which is an easy to understand function ofp^n
. I think what Fpbar basically use "z%s"%n, where you specify z explicitly.
 I am strongly against #17569 without some new idea. In the first benchmark I tried, arithmetic in Fpbar was 10 times slower than in GF (that was going to be the punchline of the sage worksheet I linked to). Do you really want
GF(3^2, 'a')
to be 30 times faster thanGF(3^2)
? I didn't think so. Even in David Roe's less unfavorable example, there was a factor of 23 difference.
comment:8 in reply to: ↑ 7 Changed 5 years ago by
Replying to was:
Some points:
 Background:
conway=True
would be absurd, because computing the conway polynomial representation of a finite field is *incredibly* hard in general.
Nobody computes them on the fly. GAP stores them, for fields of order up to 2^{16} or so.
comment:9 in reply to: ↑ 7 ; followup: ↓ 10 Changed 5 years ago by
Replying to was:
Some points:
 Background:
conway=True
would be absurd, because computing the conway polynomial representation of a finite field is *incredibly* hard in general.
Yes, that's why we use pseudoConway polynomials, which drop the condition of lexicographically least. They're still nontrivial to compute, especially when the exponent has lots of divisors. But, as Dima mentions, at least we have lookup tables for small values.
 Using 'a' (or 'x') everywhere as the default is not so good; I did exactly that with number fields back in 20042006 and it caused confusion and people hated it. You easily end up with several different things that all print the same way (magma has this problem now, where everything prints as $.1; but in Magma, you can change the name after creation, as they have no coercion model or reason for not allowing changing the names). I would recommend using something like
"a%s"%(p^n)
or"a_%s_%s"%(p,n)
or"a%s_%s"%(p,n)
, which is an easy to understand function ofp^n
. I think what Fpbar basically use "z%s"%n, where you specify z explicitly.
I don't have a strong preference between "z%s"%n
and "a%s_%s"%(p,n)
, but I agree that 'a'
and 'x'
are not right as defaults.
 I am strongly against #17569 without some new idea. In the first benchmark I tried, arithmetic in Fpbar was 10 times slower than in GF (that was going to be the punchline of the sage worksheet I linked to). Do you really want
GF(3^2, 'a')
to be 30 times faster thanGF(3^2)
? I didn't think so. Even in David Roe's less unfavorable example, there was a factor of 23 difference.
Was the difference in field creation time or in arithmetic time? Because the resulting fields of these two processes should be essentially the same (with different defining polynomial perhaps).
Another possibility would be to only allow GF(p^n)
when we have an actual Conway polynomial at hand. This is a bit annoying though: someone may write code that works for small field sizes and then breaks when the field size increases. Print a warning??
comment:10 in reply to: ↑ 9 ; followup: ↓ 11 Changed 5 years ago by
Replying to roed:
Replying to was:
Some points:
 Background:
conway=True
would be absurd, because computing the conway polynomial representation of a finite field is *incredibly* hard in general.Yes, that's why we use pseudoConway polynomials, which drop the condition of lexicographically least. They're still nontrivial to compute, especially when the exponent has lots of divisors. But, as Dima mentions, at least we have lookup tables for small values.
OK, I see. For Fpbar do you always use pseudoConway polynomials?
 I am strongly against #17569 without some new idea. In the first benchmark I tried, arithmetic in Fpbar was 10 times slower than in GF (that was going to be the punchline of the sage worksheet I linked to). Do you really want
GF(3^2, 'a')
to be 30 times faster thanGF(3^2)
? I didn't think so. Even in David Roe's less unfavorable example, there was a factor of 23 difference.Was the difference in field creation time or in arithmetic time? Because the resulting fields of these two processes should be essentially the same (with different defining polynomial perhaps).
I was testing arithmetic. However, I definitely made a mistake, because I just tried again, and the timing for arithmetic is *identical*, just as you say (which is very cool).
Thus I reverse my position: instead, I'm personally fine with #17569, with the caveat that I'm a little nervous about the pseudoConway polynomials....
Did anybody write up how Fpbar works somewhere? (I'm teaching computational number theory and it would be fun to talk about this.)
comment:11 in reply to: ↑ 10 ; followup: ↓ 13 Changed 5 years ago by
Did anybody write up how Fpbar works somewhere? (I'm teaching computational number theory and it would be fun to talk about this.)
I don't want to ruin the fun but this is a trac ticket in needs_review
, not a forum.
Nathann
comment:12 Changed 5 years ago by
 Commit changed from f96f09f848e3b9877aa50c4d4c26557e2181a9fd to e0259bf16f00e08b86e5bb743cf1df76b578e1aa
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
e0259bf  trac #19929: GF(16) (without explicit variable name)

comment:13 in reply to: ↑ 11 ; followups: ↓ 14 ↓ 16 Changed 5 years ago by
comment:14 in reply to: ↑ 13 ; followup: ↓ 15 Changed 5 years ago by
 Milestone changed from sage7.1 to sageduplicate/invalid/wontfix
 Status changed from needs_review to positive_review
I emailed William offline. #17569 now needs review.
Fantastic !
As was bargained before, let me close this ticket :)
Thanks,
Nathann
comment:15 in reply to: ↑ 14 Changed 5 years ago by
comment:16 in reply to: ↑ 13 ; followup: ↓ 17 Changed 5 years ago by
Replying to roed:
Replying to ncohen:
Did anybody write up how Fpbar works somewhere? (I'm teaching computational number theory and it would be fun to talk about this.)
I don't want to ruin the fun but this is a trac ticket in
needs_review
, not a forum.I emailed William offline. #17569 now needs review.
For anybody who finds this via a google search, here's what David said, which is very relevant for understanding the tradeoffs in this very ticket and why one should expect constructing GF(p^n)
via what is at #175569 to be potentially significantly slower than just GF(p^n,'a')
: " don't think any of us wrote up pseudoConway polynomials in particular, since most of the actual algorithms are simple modifications of the ones for Conway polynomials. For details, see
sage/rings/finite_rings/conway_polynomials.py
especially the docstrings for PseudoConwayLattice?, PseudoConwayLattice?.polynomial. _frobenius_shift is also needed, but a bit fiddly."
First this  for me it takes over 20 times longer to make the algebraic closure version:
p = next_prime(10^12) %time GF(p^6, 'a') %time GF(p).algebraic_closure().subfield(6)
Increasing 6 quickly makes it take an arbitrarily large factor longer. This is precisely the sort of thing that will seriously piss off some cryptographers someday. And they will yell at me personally.
Next this  it takes infinitely longer to make the algebraic closure version (due to a bug):
p = next_prime(10^12) %time GF(p^6, 'a') %time GF(p).algebraic_closure().subfield(6)
I'm using sage6.9.
For anybody curious about the benchmark issues I mentioned, I was benchmarking arithmetic, say "a + b", where a and b are generators of GF(9) and GF(27), respectively, using timeit. Using Fpbar this takes about 30 times as long as doing exactly the same computation after defining explicit field homomorphisms between nonFpbar finite fields. So probably Fpbar doesn't cache some sort of basic information about embeddings. This is another motivation to support K.embeddings(G) for any fields K and G, since though it's not quite as simple, in practice it can be much faster.
comment:17 in reply to: ↑ 16 Changed 5 years ago by
Replying to was:
Replying to roed:
Replying to ncohen:
Did anybody write up how Fpbar works somewhere? (I'm teaching computational number theory and it would be fun to talk about this.)
I don't want to ruin the fun but this is a trac ticket in
needs_review
, not a forum.I emailed William offline. #17569 now needs review.
For anybody who finds this via a google search, here's what David said, which is very relevant for understanding the tradeoffs in this very ticket and why one should expect constructing
GF(p^n)
via what is at #175569 to be potentially significantly slower than justGF(p^n,'a')
: " don't think any of us wrote up pseudoConway polynomials in particular, since most of the actual algorithms are simple modifications of the ones for Conway polynomials. For details, see sage/rings/finite_rings/conway_polynomials.py especially the docstrings for PseudoConwayLattice?, PseudoConwayLattice?.polynomial. _frobenius_shift is also needed, but a bit fiddly."First this  for me it takes over 20 times longer to make the algebraic closure version:
p = next_prime(10^12) %time GF(p^6, 'a') %time GF(p).algebraic_closure().subfield(6)Increasing 6 quickly makes it take an arbitrarily large factor longer. This is precisely the sort of thing that will seriously piss off some cryptographers someday. And they will yell at me personally.
I've tried to make it clear in the documentation for GF that this will happen. I'm sure that there are ways to speed up the PseudoConwayLattice
code, since nobody has spent time optimizing it, but it will always be slower than just searching for an arbitrary irreducible polynomial. That ability is still available, as long as you just specify a variable name.
Next this  it takes infinitely longer to make the algebraic closure version (due to a bug):
p = next_prime(10^12) %time GF(p^6, 'a') %time GF(p).algebraic_closure().subfield(6)I'm using sage6.9.
For anybody curious about the benchmark issues I mentioned, I was benchmarking arithmetic, say "a + b", where a and b are generators of GF(9) and GF(27), respectively, using timeit. Using Fpbar this takes about 30 times as long as doing exactly the same computation after defining explicit field homomorphisms between nonFpbar finite fields. So probably Fpbar doesn't cache some sort of basic information about embeddings. This is another motivation to support K.embeddings(G) for any fields K and G, since though it's not quite as simple, in practice it can be much faster.
comment:18 Changed 5 years ago by
 Resolution set to duplicate
 Status changed from positive_review to closed
New commits:
trac #19929: GF(16) (without explicit variable name)