Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Eisenstein integers #118

Closed
Bodigrim opened this issue Jul 31, 2018 · 1 comment · Fixed by #121
Closed

Eisenstein integers #118

Bodigrim opened this issue Jul 31, 2018 · 1 comment · Fixed by #121

Comments

@Bodigrim
Copy link
Owner

My feeling is that currently #73 is too broad and too vague. We should rather explore more special cases to hone API before taking a stab at the general problem.

We have already implemented the simplest quadratic ring, which is the ring of Gaussian integers. The next step is to handle the ring of Eisenstein integers.

The API may follow the outline of Math.NumberTheory.GaussianIntegers. Required mathematical background can be found here:
@rockbmb
Copy link
Contributor

rockbmb commented Aug 7, 2018

Sounds like an interesting issue, I'll put this in my TODO list.

rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 9, 2018
@rockbmb
[Bodigrim#118] Add Eisenstein integers module
6bd0649
@rockbmb rockbmb mentioned this issue Aug 9, 2018
Merged
7 tasks
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 9, 2018
@rockbmb
[Bodigrim#118] Add Eisenstein integers module
bd3e9e3
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 10, 2018
@rockbmb
[Bodigrim#118] Fix EisensteinInteger's Num instance
d444061
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 11, 2018
@rockbmb
[Bodigrim#118] Fix EisensteinInteger's Num instance (WIP)
ddfe9f7
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 12, 2018
@rockbmb
[Bodigrim#118] Add division for EisensteinIntegers
c09ca13 
The `Num EisensteinInteger` instance now works properly, and
there is now division over the Euclidean domain of
`EisensteinIntegers`.
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 12, 2018
@rockbmb
[Bodigrim#118] Add test to
f7edc1a
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 12, 2018
@rockbmb
[Bodigrim#118] Add test to divModE
bf881e7
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 13, 2018
@rockbmb
[Bodigrim#118] Add Eisenstein integers module
aa1a97e
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 13, 2018
@rockbmb
[Bodigrim#118] Add division for EisensteinIntegers
3b481b2 
The `Num EisensteinInteger` instance now works properly, and
there is now division over the Euclidean domain of
`EisensteinIntegers`.
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 13, 2018
@rockbmb
[Bodigrim#118] Add test to divModE
76d2415
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 15, 2018
@rockbmb
[Bodigrim#118] Add test to divModE
ed67f86 
The tests for `divModE` fail, so the reason for the function's
incorrect behavior is under investigation.

`divModE'` is a similar division algorith used for
`GaussianIntegers` that works, if no other way to fix the
current process used by `divModE`, `divModE'` will be
used instead.
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 16, 2018
@rockbmb
[Bodigrim#118] Add test to divModE
f5352ef 
The tests for `divModE` fail, so the reason for the function's
incorrect behavior is under investigation.

`divModE'` is a similar division algorith used for
`GaussianIntegers` that works, if no other way to fix the
current process used by `divModE`, `divModE'` will be
used instead.
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 16, 2018
@rockbmb
[Bodigrim#118] Fix Eisenstein integer's division algorithm
78f003e
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 16, 2018
@rockbmb
[Bodigrim#118] Add test to divModE
a4311f3 
The tests for `divModE` fail, the reason for the function's
incorrect behavior is under investigation.

`divModE'` is a similar division algorith used for
`GaussianIntegers` that works, if no other way to fix the
current process used by `divModE`, `divModE'` will be
used instead.
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 16, 2018
@rockbmb
[Bodigrim#118] Fix Eisenstein integer's division algorithm
ec8b748
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 16, 2018
@rockbmb
[Bodigrim#118]Add primality testing for Eisenstein integers
facb0b3
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 16, 2018
@rockbmb
[Bodigrim#118] Add primality testing for Eisenstein integers
4691ff5
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 16, 2018
@rockbmb
[Bodigrim#118] Add primality testing for Eisenstein integers
4c51cc8
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 16, 2018
@rockbmb
[Bodigrim#118] Add gcd for Eisenstein integers
7db763c
@rockbmb rockbmb mentioned this issue Aug 21, 2018
Closed
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 22, 2018
@rockbmb
[Bodigrim#118] Add primality testing for Eisenstein integers
5e19009
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 22, 2018
@rockbmb
[Bodigrim#118] Add gcd for Eisenstein integers
7f2f5c9
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 22, 2018
@rockbmb
[Bodigrim#118] Add primality testing for Eisenstein integers
7c83b92
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 22, 2018
@rockbmb
[Bodigrim#118] Add gcd for Eisenstein integers
673db26
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 23, 2018
@rockbmb
[Bodigrim#118] Add findPrime function
2e17dc4 
In addition, the `isPrime` function has been fixed as it
contained two errors.

- Firstly, it checked if the norm of
an Eisenstein integer was congruent to 0 modulo 3, which
is not necessary because it is supposed to be a prime
integer.

- Secondly, it did not account for the possibility of an
Eisenstein integer being the product of an integer prime
and an Eisenstein unit. For example, `isPrime 11` would be
`True`, but `isPrime $ 11 * (1 + ω)` would be `False`, which
is incorrect.
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 23, 2018
@rockbmb
[Bodigrim#118] Add findPrime function
08f21f5 
In addition, the `isPrime` function has been fixed as it
contained two errors.

- Firstly, it checked if the norm of
an Eisenstein integer was congruent to 0 modulo 3, which
is not necessary because it is supposed to be a prime
integer. This is only valid for `1 - ω`, which has been
moved into its own patter match.

- Secondly, it did not account for the possibility of an
Eisenstein integer being the product of an integer prime
and an Eisenstein unit. For example, `isPrime 11` would be
`True`, but `isPrime $ 11 * (1 + ω)` would be `False`, which
is incorrect.
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 23, 2018
@rockbmb
[Bodigrim#118] Generate infinite list of Eisenstein primes
4565a41
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 23, 2018
@rockbmb
[Bodigrim#118] Add tests to primes
fc8e9a6
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 24, 2018
@rockbmb
[Bodigrim#118] Add Eisenstein integer factorisation (WIP)
1f576f8
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 24, 2018
@rockbmb
[Bodigrim#118] Add Eisenstein integer factorisation
faab321
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 24, 2018
@rockbmb
[Bodigrim#118] Add one more factorisation test
46cb513 
There is now a test to verify that a factorisation only produces
primary Eisenstein prime factors.
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 24, 2018
@rockbmb
[Bodigrim#118] Add test to verify sign of primes produced by primes
d9a9b9f
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 24, 2018
@rockbmb
[Bodigrim#118] Improve comment for factorise
e006565
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 24, 2018
@rockbmb
[Bodigrim#118] Add comment to quotEvenI
71dd575
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 24, 2018
@rockbmb
[Bodigrim#118] Improve findPrime's comment
9877dc0
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 25, 2018
@rockbmb
[Bodigrim#118] Add Eisenstein integer benchmark module
7996d9a
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 26, 2018
@rockbmb
[Bodigrim#118] Made Eisenstein GCD faster (WIP)
fcee5b1
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 26, 2018
@rockbmb
[Bodigrim#118] Improve Eisenstein GCD
635be23 
Using a method described in
[Efficient algorithms for the gcd and cubic residuosity in
the ring of Eisenstein integers]
(https://core.ac.uk/download/pdf/82554035.pdf),
the algorithm used to calculate the `gcd` between Eisenstein
integers was refactored.
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 27, 2018
@rockbmb
[Bodigrim#118] Improve Eisenstein GCD
1b5306c 
Using a method described in
[Efficient algorithms for the gcd and cubic residuosity in
the ring of Eisenstein integers]
(https://core.ac.uk/download/pdf/82554035.pdf),
the algorithm used to calculate the `gcd` between Eisenstein
integers was refactored.
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 28, 2018
@rockbmb
[Bodigrim#118] Revert GCD's algorithm
ce6085f 
The `Math.NumberTheory.EisensteinIntegers.gcdE` function
was changed to use the previous algorithm.
rockbmb added a commit to rockbmb/arithmoi that referenced this issue Aug 28, 2018
@rockbmb
[Bodigrim#118] Revert GCD's algorithm
112fd43 
The `Math.NumberTheory.EisensteinIntegers.gcdE` function
was changed to use the previous algorithm.
Bodigrim added a commit that referenced this issue Aug 29, 2018
@Bodigrim
Merge pull request #121 from rockbmb/eisenstein-integers
e31769d 
[#118] Add Eisenstein integers module
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

[#118] Add Eisenstein integers module rockbmb/arithmoi
2 participants
@Bodigrim @rockbmb