Questions tagged [computational-number-theory]
This tag is for questions regarding to computational number theory, the branch of number theory concerned with finding and implementing efficient computer algorithms for solving various problems in number theory.
46
questions
0
votes
0
answers
63
views
gcrd and Associates of an element of the Quaternion algebra over a totally real number field $K$
Let $K$ be a totally real number field of class number 1, and $Q$ the quaternion algebra over the ring of integers of $K$ with basis
$\{1,i,j,k\}$ such that $i^2 = j^2 = k^2 = -1$ and $ij = -ji, ik = ...
- 191
0
votes
0
answers
33
views
Real Life Applications of Two-Variable Quadratic Formulas
Where do two-variable quadratic formulas show up today as real-life combinatorial complexity challenges? Weather? Particle motion? Celestial calculations? Routing? Does anyone have specific examples? ...
- 1
1
vote
0
answers
40
views
Requesting for the Reference of multiplicative Property for Resultants [duplicate]
I have learned the definition of the Resultant of two polynomials Resultant of two polynomials. Following this definition, I want to see the proof of one property described in the "Characterizing ...
- 2,215
1
vote
1
answer
75
views
Resultant $\mathrm{Res}_{x}(f(x), y - g(x))$ calculation and divisibility by $f$
I have learned the definition of the Resultant of two polynomials Resultant of two polynomials. In most places, it is defined over a field. Can we similarly define it for the general ring, for example,...
- 2,215
17
votes
3
answers
1k
views
One of the numbers $\zeta(5), \zeta(7), \zeta(9), \zeta(11)$ is irrational
I am reading an interesting paper One of the numbers ζ(5), ζ(7), ζ(9), ζ(11) is irrational by Zudilin. We fix odd numbers $q$ and $r$, $q\geq r+4$ and a tuple $\eta_0,\eta_1,...,\eta_q$ of positive ...
- 910
3
votes
1
answer
47
views
Understanding what 'LLL-reduced in the direction of v' means
I've been working with ideal reduction algorithms, and in particular have a need to understand the notion of LLL-reduced along a vector $v$, and in particular what it actually means to have 'small $v$-...
- 197
3
votes
0
answers
592
views
Factoring integers using trigonometric integrals
In this post, I want to ask the community about an issue regarding an analytical approach to dealing with the integer factorization problem.
The problem definition is as follows:
1. Sets
Let $C=\{x^2:...
- 51
0
votes
0
answers
120
views
euler totient approximation
I want to find an approximation of Euler's totient.
It`s for product n of two prime number a and b
This is what I have actually:
\begin{array}{}
n = a.b\\
\varphi(n) = a.b - a - b + 1\\
\varphi(n) \...
0
votes
1
answer
132
views
Prove correctness of algorithm that computes $\lfloor \sqrt{n}\rfloor$
I was looking in V. Shoup's book 'A Computational Introduction to Number Theory and Algebra' (freely available here). The exercise is as follows:
As I'm not very familiar with proving correctness of ...
user555661
0
votes
0
answers
19
views
Condition on the minimality of Minkowski units
I am interested in to undrestand when the Minkowski units in real biquadratic number fields are minimal in the log unit lattices. I have read some pieces of literature online which are investigating ...
- 79
2
votes
1
answer
117
views
Computing coefficients of $E_4^n$
This is a question about computing coefficients of modular forms, in particular about $E_4^4$, or $E_4^n$. Just a disclaimer, I am quite a beginner in this subject, and I am still slowly learning ...
- 3,772
0
votes
0
answers
66
views
Calculating modular roots over Gaussian integers
Let $a+bi$ be a Gaussian integer.
Given another Gaussian integer $c+di$ how does one find $x^2\equiv(c+di)\bmod(a+bi)$?
Can you illustrate with $x^2\equiv 48\bmod(156\pm89i)$?
- 6,245
1
vote
0
answers
313
views
Finding Elliptic Curve based on Multiplicity and rational coordinates
We have to find an elliptic curve $E:= y^2=x^3+Ax+B $ (A, B are integers) which has points $P, Q$ with rational coordinates and satisfy $P=[n]Q, n>1$. So,
Input: Rational coordinates = $P$.
Output: ...
1
vote
0
answers
67
views
Most efficient way to count primeomega(n)=4?
Problem:
Given natural number N, count $\sum_{k\le N} [{\omega(k)=4}]$
This is the sequence of $\omega(k)=4$, we don't need to generate the sequence. Given a $N$, we need to know number of numbers in ...
- 470
4
votes
1
answer
182
views
Calculate $ \sum_{k=1}^{n} k\cdot \mu(k) $
Problem:
Given $n$, Calculate $ \sum_{k=1}^{n} k\cdot \mu(k) $
This is the oeis series.
My Thoughts:
I need a sublinear algo, possibly something of the order of $n^{3/4}$ or $n^{2/3}$ time. Any ...
- 470