# 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
Filter by
Sorted by
Tagged with
63 views

• 51
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) \...
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 ...
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
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
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
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
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 ...
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 ...
247 views

### Calculate $\sum_{k=1}^{n} k\cdot\varphi(k)$

Problem: Given $n$, Calculate $\sum_{k=1}^{n} k\cdot \varphi(k)$ This is the oeis series. My Thoughts: Oeis gives a couple of approximate estimates/asymptotics but no real formula, exact closed form ...
1 vote
96 views

### Sum of co-primes of a number $n \le k$

Problem Given a number $n$ and a number $k$ ($k\leq n$) we are to find sum of co-primes of $n$ less than or equal to $k$ My thoughts factorise $n$ and then do $k(k + 1)/2$ - ...
227 views

• 638
42 views

• 5,847
491 views

### Efficient summation of multiplicative functions on intervals

Suppose that $f: \mathbb{N} \to \mathbb{C}$ is a multiplicative function; i.e., $f(mn) = f(m)f(n)$ if $m, n$ are coprime. I'm interested in efficiently calculating sums of the form $\sum_{k=1}^N f(k)$...
• 1,103
59 views

### Division in higher dimensional ring of formal power series

Let $R$ be a ring with characteristic $0$. We can assume $R$ to be the $p$-adic field also, which is of course characteristic $0$. Let $f(x) \in R[[x]]$ be a power series and $f^{k}(x)$ be its $k$-th ...
• 10.8k
150 views

### What are the mathematics journals focus on computational research article in number theory or algebra?

I know $\text{Mathematics of Computation(AMS)}$ is journal aiming research articles consisting of lots of computations. But this is one of the highest journals in this area to my knowledge. Is there ...
• 10.8k
324 views

### Study and research in computational number theory

I am an undergraduate student and i have completed courses like data structures and algorithms , discrete mathematics , elementary number theory (i have studied Burton's book completely), abstract ...
347 views

### How to find inverse of elements in a very large $\mathbb{Z}_n$ group?

Suppose I have an element $a\in\mathbb{Z}_n$ where $n$ is thousands of digits(base 10) and $\gcd(a,n)=1$. Is there a computationally efficient way of finding the inverse of $a$? or just any way to ...
• 1,074
Using the formula $$\left(\frac{a}{p}\right) \equiv a^{\frac{p - 1}{2}} \pmod{p}$$ for the Legendre symbol $\left(\frac{a}{p}\right),$ it takes only $O(\log p)$ steps to compute $\left(\frac{a}{p}\... 2 votes 1 answer 92 views ### Variations of random coprime integers probability The probability for two random integers to be coprime is$\frac{6}{\pi^2}$(see for example this post), that is about$61\%$. After some computations, for$u_i, v_i$random integers, the probability ... • 5,847 4 votes 1 answer 218 views ### Longest consecutive runs of sums of$k$-subsets of first$n$primes Table of contents [$1.$] Definition [$2.$] Implication. (Motivation.) [$3.$] Question. & Computed data. [$4.$] Solutions of simplified variations. [$5.$] Progress on solving the question. [$6.$] ... • 12.5k 3 votes 1 answer 160 views ### Factoring Sieve Polynomial I am dealing with a polynomial of the form $$p(a,b) = a^n - b^n$$ for integer values$a > b$, and some small integer$n$. I am wanting to factor this polynomial for a large range of values (for ... 3 votes 1 answer 121 views ### generating function of sum of divisors function It is well known that the function $$\sigma_k(n)=\sum_{d|n}d^k$$ has a generating function. For a number field$K$, suppose that$\mathfrak{a}, \mathfrak{b}$are ideals in some ideal class$C$and ... • 41 1 vote 1 answer 52 views ### how to split a separable algebra? I'm trying to factor ideals in a function field (more precisely, ideals in a maximal order of a function field), and I've come across a step in the published Buchman-Lenstra algorithm which works in ... 1 vote 1 answer 68 views ### Probability the Fermat test returns "probably prime" We aim to show that probability of odd$n>1$passing the Fermat test for all bases a coprime to n is $$\frac{1}{\phi(n)}\prod_{p|n, p \ prime}gcd(p-1,n-1)$$where$\phi$is the Euler totient ... • 344 0 votes 0 answers 149 views ### Testing whether two number fields are isomorphic Could somebody point me to an implementation of an algorithm that takes two number fields$F$and$L\$, tests whether they are isomorphics, and if they are, returns an isomorphism? There is such a ...
In a recent press release off the Great Internet Mersenne Prime Search distributed computing project page, it is announced that $$2^{82589933} - 1$$ is the largest known (Mersenne) prime, ...