0
$\begingroup$

1.start from multiplicative group modulus N where N is odd. 2.take all elements of subgroup with generator equal 2.

question : what do you need to know about N (factorization,phi) for fast calculation of total sum of all subgroup elements.

known facts : it is easy to prove , it equal to K*N

it is somehow related to phi(N)

related problems : number of odd elements, number of elements less than (N-1)/2.0 difference between number of odd and even elements - in most cases is not 0.

how calculate K?

example : 35 1,2,4,8,16,32,29,23,11,22,9,18 = 175 = 5*35 even : 7,odd : 5 , 7-5=2

is it related somehow to modular functions(forms)?

fast : O(log n) or something similar ,O(phi(n)) Is very slow.

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ I think even if $N$ is prime you need to know the order of $2$ modulo $N$, and there's no known fast way to compute that. $\endgroup$
    – Gerry Myerson
    Commented Oct 9, 2020 at 6:45
  • $\begingroup$ if $N$ is prime, factorization of $N-1$ is not “slow” problem.Then just check division 2 ** factors - 1 by $N$ $\endgroup$
    – user6690
    Commented Oct 9, 2020 at 12:52
  • $\begingroup$ If the equation $2^j\equiv -1$ (mod $n$) has a solution, then $k=\frac 12 \mathrm{ord}_n(2)$, where $\mathrm{ord}_n(2)$ denotes the order of 2 modulo $n$. This is because the powers of 2 come in pairs $c,n-c$. $\endgroup$
    – Richard Stanley
    Commented Oct 9, 2020 at 17:05
  • $\begingroup$ @user6690 The equation $2^j\equiv -1$ (mod 35) does not have a solution, so $n=35$ is not a counterexample. $\endgroup$
    – Richard Stanley
    Commented Oct 9, 2020 at 17:18
  • $\begingroup$ thank you, but it is trivial case - odd == even. N = 35, no solution. $\endgroup$
    – user6690
    Commented Oct 9, 2020 at 17:20

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .