hermann on Mon, 02 Oct 2023 20:39:04 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

How to generate wolframscript "PowersRepresentations[...]" output in PARI/GP


https://reference.wolfram.com/language/ref/PowersRepresentations.html
"PowersRepresentations[n,k,p]
    gives the distinct representations of the integer n as
    a sum of k non-negative p^(th) integer powers."

I searched for all hits for "powers" and "representations" in GP user
manual and found nothing. How to compute sum of 4 squares of here
17*29 semiprime with PARI/GP by using any builtin function?

(wolframscript is free for Raspberry SBCs)

pi@raspberrypi400:~ $ wolframscript
Wolfram Language 13.3.1 Engine for Linux ARM (64-bit)
Copyright 1988-2023 Wolfram Research, Inc.

In[1]:= PowersRepresentations[17*29,4,2]

Out[1]= {{0, 0, 3, 22}, {0, 0, 13, 18}, {0, 4, 6, 21}, {0, 5, 12, 18},

   {1, 2, 2, 22}, {1, 10, 14, 14}, {2, 2, 14, 17}, {2, 5, 8, 20},

   {2, 8, 8, 19}, {2, 8, 13, 16}, {2, 10, 10, 17}, {3, 4, 12, 18},

   {3, 12, 12, 14}, {4, 4, 10, 19}, {4, 5, 14, 16}, {4, 10, 11, 16},

   {6, 6, 14, 15}, {6, 12, 12, 13}, {8, 8, 13, 14}}

In[2]:=



I can create one sum of 4 squares for factored RSA numbers.
Instead of using known RSA numbers, I can pass arbitrary
semiprime p*q by passing [0,0,p,q]:


hermann@7600x:~/RSA_numbers_factored/pari$ gp -q RSA_numbers_factored.gp
? RSA.square_sums_4([0,0,17,29])
[20, 2, 8, 5]
? sq2(17)
[4, 1]
? sq2(29)
[5, 2]
?

Last line of GP implementation explains how to compute it
from two sum of two squares for the prime p and q:

RSA.square_sums_4=x->{
\\  """
...
\\  """
    my(r=self.get_(x),p,q);
    assert(has_factors(r));
    my([,,p,q]=r);
    assert(p%4==1&&q%4==1);
    P=sq2(p);
    Q=sq2(q);
    return([P[1]*Q[1],P[2]*Q[2],P[1]*Q[2],P[2]*Q[1]]);


Regards,

Hermann.