Questions tagged [computational-number-theory]

Computational Number Theory is for explicit calculations or algorithms involving anything of interest to number theorists.

463 questions
Filter by
Sorted by
Tagged with
265 views

Efficiently computing $\prod_{i=1}^{n} A_i$

Let $k$ be a nonnegative integer, how to compute $\prod\limits_{i=1}^{n} A_i$ quickly and accurately, where $$A_i=\begin{bmatrix} 0 & 1\\ i^k & 1 \end{bmatrix}?$$ I know if $k=0$, we can use ...
• 696
503 views

• 83
103 views

Record for determining complete list of imaginary quadratic fields with small class number

In 2003, Mark Watkins (Class numbers of imaginary quadratic fields) determined all imaginary quadratic fields having class number at most 100. Has this list been improved? That is, what is the largest ...
• 26.6k
142 views

• 1,085
176 views

How to construct an explicit isomorphism of the split Quaternion Algebra $(a,b)_F$ over the field $F$ to $\mathrm{Mat}_2(F)$

$\DeclareMathOperator\Mat{Mat}$How to construct an explicit isomorphism of the split quaternion algebra $(a,b)_F$ over the field $F$ to $\Mat_2(F)$? As it is known that the algebra of quaternions is ...
312 views

• 12.8k
2k views

• 403
203 views

Is there a Bailey–Borwein–Plouffe (BBP) formula for $\gamma$ (euler-mascheroni constant)?

I was reading about BBP type formulas and there was a lot about $\pi$ and some $\log$'s. I started searching for some other constants and could find $2$ formulas for the catalan constant and learned ...
• 521
313 views

Can you confirm the positivity of a quantity involving the Stirling numbers of the first kind

Let $s(m,n)$ denote the Stirling numbers of the first kind. For $m,n\in\mathbb{N}$, define \mathcal{Q}(m,n)=(-1)^n\sum_{\ell=0}^{2n} \binom{m+\ell-1}{m-1} s(m+2n-1,m+\ell-1)\biggl(\...
• 985
134 views

Road map for learning about the computational/general theory of modular curves/isogenies of abelian varieties for cryptography

I am a graduate math/crypto student. So I've had some free time last year and I heard about elliptic curves in cryptography and how a resilient cryptosystem got demolished by a spectacular attack ...
184 views

Efficiently count the number of primitive roots in all moduli up to $n$

Let's define $f(n)$ as the number of primitive roots modulo $n$. That is, $f(n) = \begin{cases}\varphi(\varphi(n))&n=1,2,4,p^k,2p^k\\0&\text{otherwise}\end{cases}$. We want to efficiently ...
• 3,299
213 views

Newton type method for finite fields?

I have a polynomial $p(x)$ in $\mathbb{Z}/q\mathbb{Z}$ that is easy to compute for any $x$ but has an absurdly large degree $d > 2^{256}$. I know for a fact that it has a zero and I would like to ...
• 591
1 vote