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: sage-duplicate/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:

Status badges

Description (last modified by ncohen)

This branch is related to the following sage-devel conversation:

https://groups.google.com/d/topic/sage-devel/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 ncohen

  • Description modified (diff)

comment:2 Changed 5 years ago by ncohen

  • Branch set to public/19929
  • Cc cremona dimpase vdelecroix added
  • Commit set to f96f09f848e3b9877aa50c4d4c26557e2181a9fd
  • Status changed from new to needs_review

New commits:

f96f09ftrac #19929: GF(16) (without explicit variable name)

comment:3 follow-up: Changed 5 years ago by roed

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 ; follow-up: Changed 5 years ago by 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.

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 roed

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 ncohen

Thanks,

Nathann

comment:7 follow-ups: Changed 5 years ago by was

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 2004-2006 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 of p^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 than GF(3^2)? I didn't think so. Even in David Roe's less unfavorable example, there was a factor of 2-3 difference.
Last edited 5 years ago by was (previous) (diff)

comment:8 in reply to: ↑ 7 Changed 5 years ago by dimpase

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 216 or so.

comment:9 in reply to: ↑ 7 ; follow-up: Changed 5 years ago by 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 pseudo-Conway 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 2004-2006 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 of p^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 than GF(3^2)? I didn't think so. Even in David Roe's less unfavorable example, there was a factor of 2-3 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 ; follow-up: Changed 5 years ago by was

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 pseudo-Conway 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 pseudo-Conway 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 than GF(3^2)? I didn't think so. Even in David Roe's less unfavorable example, there was a factor of 2-3 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).

https://cloud.sagemath.com/projects/4a5f0542-5873-4eed-a85c-a18c706e8bcd/files/support/2016-01-21-114547-GF-speed.sagews

Thus I reverse my position: instead, I'm personally fine with #17569, with the caveat that I'm a little nervous about the pseudo-Conway 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 ; follow-up: Changed 5 years ago by 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.

Nathann

comment:12 Changed 5 years ago by git

  • Commit changed from f96f09f848e3b9877aa50c4d4c26557e2181a9fd to e0259bf16f00e08b86e5bb743cf1df76b578e1aa

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

e0259bftrac #19929: GF(16) (without explicit variable name)

comment:13 in reply to: ↑ 11 ; follow-ups: Changed 5 years ago by 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 e-mailed William offline. #17569 now needs review.

Nathann

comment:14 in reply to: ↑ 13 ; follow-up: Changed 5 years ago by ncohen

  • Milestone changed from sage-7.1 to sage-duplicate/invalid/wontfix
  • Status changed from needs_review to positive_review

I e-mailed 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 roed

Replying to ncohen:

I e-mailed William offline. #17569 now needs review.

Fantastic !

As was bargained before, let me close this ticket :-)

Thanks,

You're welcome. :-) It had definitely been sitting there too long, and was a pretty easy change.

Nathann

comment:16 in reply to: ↑ 13 ; follow-up: Changed 5 years ago by 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 e-mailed 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 pseudo-Conway 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 sage-6.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 non-Fpbar 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 roed

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 e-mailed 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 pseudo-Conway 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 sage-6.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 non-Fpbar 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 vbraun

  • Resolution set to duplicate
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.