Topic: Prime test functions
Author: Alexander Zaitsev <zamazan4ik@gmail.com>
Date: Sun, 11 Feb 2018 12:09:53 -0800 (PST)
Raw View
------=_Part_8253_62567644.1518379793706
Content-Type: multipart/alternative;
boundary="----=_Part_8254_637615256.1518379793706"
------=_Part_8254_637615256.1518379793706
Content-Type: text/plain; charset="UTF-8"
Hello,
I want to get feedback about my proposal about adding prime test functions
to C++. You can find it as an attached file.
Open questions:
- I am not sure about interface for is_probable_prime interface. On the
one hand i don't want to see under the hood any specific imeplementation.
On the other hand i should guarantee something (I mean complexity and
probablity).
Do you have any suggestions?
--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/fc678dff-6bec-4f54-bb7b-22e140b54d71%40isocpp.org.
------=_Part_8254_637615256.1518379793706
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">Hello,<div><br></div><div>I want to get feedback about my =
proposal about adding prime test functions to C++. You can find it as an at=
tached file.</div><div><br></div><div>Open questions:</div><div><ul><li>I a=
m not sure about interface for is_probable_prime interface. On the one hand=
i don't want to see under the hood any specific imeplementation. On th=
e other hand i should guarantee something (I mean complexity and probablity=
).</li></ul></div><div><br></div><div>Do you have any suggestions?</div><di=
v><br></div><div><br></div></div>
<p></p>
-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/fc678dff-6bec-4f54-bb7b-22e140b54d71%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/fc678dff-6bec-4f54-bb7b-22e140b54d71=
%40isocpp.org</a>.<br />
------=_Part_8254_637615256.1518379793706--
------=_Part_8253_62567644.1518379793706
Content-Type: text/html; charset=US-ASCII;
name="Proposal for PrimeTest functions.html"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="Proposal for PrimeTest functions.html"
X-Attachment-Id: d96f27ca-fee8-4529-a202-e366d6029277
Content-ID: <d96f27ca-fee8-4529-a202-e366d6029277>
<HTML><HEAD><TITLE>TODO, Proposal for Prime test functions</TITLE></HEAD><BODY>
<CENTER>
<H1><A NAME="TODO, Proposal for prime test functions">Proposal for Prime test functions</A></H1>
</CENTER>
<TABLE ALIGN="RIGHT" CELLSPACING="0" CELLPADDING="0">
<TR>
<TD ALIGN="RIGHT"><B><I>Document number:</I></B></TD>
<TD> TODO</TD>
</TR>
<TR>
<TD ALIGN="RIGHT"><B><I>Date:</I></B></TD>
<TD> TODO</TD>
</TR>
<TR>
<TD ALIGN="RIGHT"><B><I>Project:</I></B></TD>
<TD> Programming Language C++</TD>
</TR>
<TR>
<TD ALIGN="RIGHT"><B><I>Reference:</I></B></TD>
<TD> ISO/IEC IS 14882:TODO(E)</TD>
</TR>
<TR>
<TD ALIGN="RIGHT"><B><I>Reply to:</I></B></TD>
<TD> Alexander Zaitsev</TD>
</TR>
<TR>
<TD></TD>
<TD> Solarwinds</TD>
</TR>
<TR>
<TD></TD>
<TD> zamazan4ik@tut.by</TD>
</TR>
</TABLE>
<BR CLEAR="ALL">
<HR>
<H2><A NAME="Overview">Overview</A></H2>
<p>Programmers sometimes need to check whether the number is prime or not. This task is especially common in cryptography.
This proposal suggests extending the set of mathematical functions with functions to check whether the number is prime or not.</p>
<H2><A NAME="Design overview">Design overview</A></H2>
<p>This paper proposes two prime-test functions.
<H2><A NAME="cmath">Header <code><cmath></code>
synopsis</A></H2>
<pre><code>namespace std {
namespace experimental {
bool is_prime(Integral value) noexcept;
bool is_probable_prime(Integral value, Integral certainty) noexcept;
} /* namespace experimental */
} /* namespace std */
</code></pre>
<B><A NAME="std::is_prime">is_prime</A></B>
<code><pre>bool <b>is_prime</b>(Integral value) noexcept;
</pre></code>
<p>The function tests is a value prime or not. If a value is prime, returns true. Otherwise, false.</p>
<p>Complexity: at least O(sqrt(N)).</p>
<B><A NAME="std::is_probable_prime">is_probable_prime</A></B>
<code><pre>bool <b>is_probable_prime</b>(Integral value, Integral certainty) noexcept;
</pre></code>
<b>Parameters</b>:
<p>certainty - a measure of the uncertainty that the caller is willing to tolerate: if the call returns true the probability that value is prime exceeds (1 - 1/2^certainty).</p>
<p>Returns true if value is probably prime, false if it's definitely composite. If certainty is <= 0, true is returned.</p>
<p>Complexity: TODO</p>
</BODY></HTML>
------=_Part_8253_62567644.1518379793706--
.
Author: Thiago Macieira <thiago@macieira.org>
Date: Sun, 11 Feb 2018 12:55:43 -0800
Raw View
On Sunday, 11 February 2018 12:09:53 PST Alexander Zaitsev wrote:
> Hello,
>
> I want to get feedback about my proposal about adding prime test functions
> to C++. You can find it as an attached file.
>
> Open questions:
>
> - I am not sure about interface for is_probable_prime interface. On the
> one hand i don't want to see under the hood any specific imeplementation.
> On the other hand i should guarantee something (I mean complexity and
> probablity).
>
>
> Do you have any suggestions?
Please add answers to these questions:
How often is this necessary? What use-cases for it exist, besides cryptography
(which will need numbers wider than 64-bit anyway)? Does it even exist in any
modern math library?
What is the complexity if this function? Do you have a suggested
implementation for it?
--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/9150311.INAnE2rANT%40tjmaciei-mobl1.
.
Author: Alexander Zaitsev <zamazan4ik@gmail.com>
Date: Sun, 11 Feb 2018 14:04:39 -0800 (PST)
Raw View
------=_Part_8424_1246644764.1518386679604
Content-Type: multipart/alternative;
boundary="----=_Part_8425_1218662995.1518386679605"
------=_Part_8425_1218662995.1518386679605
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
=D0=B2=D0=BE=D1=81=D0=BA=D1=80=D0=B5=D1=81=D0=B5=D0=BD=D1=8C=D0=B5, 11 =D1=
=84=D0=B5=D0=B2=D1=80=D0=B0=D0=BB=D1=8F 2018 =D0=B3., 23:55:48 UTC+3 =D0=BF=
=D0=BE=D0=BB=D1=8C=D0=B7=D0=BE=D0=B2=D0=B0=D1=82=D0=B5=D0=BB=D1=8C Thiago=
=20
Macieira =D0=BD=D0=B0=D0=BF=D0=B8=D1=81=D0=B0=D0=BB:
>
> On Sunday, 11 February 2018 12:09:53 PST Alexander Zaitsev wrote:=20
> > Hello,=20
> >=20
> > I want to get feedback about my proposal about adding prime test=20
> functions=20
> > to C++. You can find it as an attached file.=20
> >=20
> > Open questions:=20
> >=20
> > - I am not sure about interface for is_probable_prime interface. On=
=20
> the=20
> > one hand i don't want to see under the hood any specific=20
> imeplementation.=20
> > On the other hand i should guarantee something (I mean complexity and=
=20
> > probablity).=20
> >=20
> >=20
> > Do you have any suggestions?=20
>
> Please add answers to these questions:=20
>
> How often is this necessary? What use-cases for it exist, besides=20
> cryptography=20
> (which will need numbers wider than 64-bit anyway)? Does it even exist in=
=20
> any=20
> modern math library?=20
>
> What is the complexity if this function? Do you have a suggested=20
> implementation for it?=20
>
> --=20
> Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org=20
> Software Architect - Intel Open Source Technology Center=20
>
>
>
>
1. Honestly, i don't know how I can measure frequency of using these=20
functions. Depends on your domain. E.g. prime numbers are widely-used in=
=20
cryptography. Also using prime numbers are required for some hash=20
techniques.
2. About numbers wider than 64 bits - we have proposals about wide_int=
=20
(http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0539r2.html) .=
=20
Also i am working on Unbounded integer. We can add interoperability with=
=20
these types later.
3. Yes, it is.=20
E.g.: https://gmplib.org/manual/Number-Theoretic-Functions.html (
*mpz_probab_prime_p*
), https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html#i=
sProbablePrime(int)
4. Question about complexities is open. Because there are a lot of=20
algorithms for prime check with different complexities. For is_prime i=
=20
added O(sqrt(N)), but there are faster algorithms. If we are talking abo=
ut=20
is_probable_prime, for now i am not sure which complexity should be chos=
en=20
here. Do you have any ideas?
5. Should i suggest complete implementation or just names of possible=20
algorithms?
--=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/d230ae55-fad0-4267-9ef2-cc861a0bfe41%40isocpp.or=
g.
------=_Part_8425_1218662995.1518386679605
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><br><br>=D0=B2=D0=BE=D1=81=D0=BA=D1=80=D0=B5=D1=81=D0=B5=
=D0=BD=D1=8C=D0=B5, 11 =D1=84=D0=B5=D0=B2=D1=80=D0=B0=D0=BB=D1=8F 2018 =D0=
=B3., 23:55:48 UTC+3 =D0=BF=D0=BE=D0=BB=D1=8C=D0=B7=D0=BE=D0=B2=D0=B0=D1=82=
=D0=B5=D0=BB=D1=8C Thiago Macieira =D0=BD=D0=B0=D0=BF=D0=B8=D1=81=D0=B0=D0=
=BB:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex=
;border-left: 1px #ccc solid;padding-left: 1ex;">On Sunday, 11 February 201=
8 12:09:53 PST Alexander Zaitsev wrote:
<br>> Hello,
<br>>=20
<br>> I want to get feedback about my proposal about adding prime test f=
unctions
<br>> to C++. You can find it as an attached file.
<br>>=20
<br>> Open questions:
<br>>=20
<br>> =C2=A0 =C2=A0- I am not sure about interface for is_probable_prime=
interface. On the
<br>> =C2=A0 =C2=A0one hand i don't want to see under the hood any s=
pecific imeplementation.
<br>> On the other hand i should guarantee something (I mean complexity =
and
<br>> probablity).
<br>>=20
<br>>=20
<br>> Do you have any suggestions?
<br>
<br>Please add answers to these questions:
<br>
<br>How often is this necessary? What use-cases for it exist, besides crypt=
ography=20
<br>(which will need numbers wider than 64-bit anyway)? Does it even exist =
in any=20
<br>modern math library?
<br>
<br>What is the complexity if this function? Do you have a suggested=20
<br>implementation for it?
<br>
<br>--=20
<br>Thiago Macieira - thiago (AT) <a href=3D"http://macieira.info" target=
=3D"_blank" rel=3D"nofollow" onmousedown=3D"this.href=3D'http://www.goo=
gle.com/url?q\x3dhttp%3A%2F%2Fmacieira.info\x26sa\x3dD\x26sntz\x3d1\x26usg\=
x3dAFQjCNEswDUBNCNanbu7euhqLn_62FW8ag';return true;" onclick=3D"this.hr=
ef=3D'http://www.google.com/url?q\x3dhttp%3A%2F%2Fmacieira.info\x26sa\x=
3dD\x26sntz\x3d1\x26usg\x3dAFQjCNEswDUBNCNanbu7euhqLn_62FW8ag';return t=
rue;">macieira.info</a> - thiago (AT) <a href=3D"http://kde.org" target=3D"=
_blank" rel=3D"nofollow" onmousedown=3D"this.href=3D'http://www.google.=
com/url?q\x3dhttp%3A%2F%2Fkde.org\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNH=
GRJdo5_JYG1DowztwAHAKs80XSA';return true;" onclick=3D"this.href=3D'=
http://www.google.com/url?q\x3dhttp%3A%2F%2Fkde.org\x26sa\x3dD\x26sntz\x3d1=
\x26usg\x3dAFQjCNHGRJdo5_JYG1DowztwAHAKs80XSA';return true;">kde.org</a=
>
<br>=C2=A0 =C2=A0Software Architect - Intel Open Source Technology Center
<br>
<br>
<br>
<br></blockquote><div><br></div><div><ol><li>Honestly, i don't know how=
I can measure frequency of using these functions. Depends on your domain. =
E.g. prime numbers are widely-used in cryptography. Also using prime number=
s are required for some hash techniques.</li><li>About numbers wider than 6=
4 bits - we have proposals about wide_int (http://www.open-std.org/jtc1/sc2=
2/wg21/docs/papers/2017/p0539r2.html) . Also i am working on Unbounded inte=
ger. We can add interoperability with these types later.<br></li><li>Yes, i=
t is. E.g.:=C2=A0https://gmplib.org/manual/Number-Theoretic-Functions.html =
(<strong style=3D"color: rgb(0, 0, 0); font-family: "Times New Roman&q=
uot;; font-size: medium;">mpz_probab_prime_p</strong>),=C2=A0https://docs.o=
racle.com/javase/7/docs/api/java/math/BigInteger.html#isProbablePrime(int)<=
/li><li>Question about complexities is open. Because there are a lot of alg=
orithms for prime check with different complexities. For is_prime i added O=
(sqrt(N)), but there are faster algorithms. If we are talking about is_prob=
able_prime, for now i am not sure which complexity should be chosen here. D=
o you have any ideas?</li><li>Should i suggest complete implementation or j=
ust names of possible algorithms?</li></ol></div></div>
<p></p>
-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/d230ae55-fad0-4267-9ef2-cc861a0bfe41%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/d230ae55-fad0-4267-9ef2-cc861a0bfe41=
%40isocpp.org</a>.<br />
------=_Part_8425_1218662995.1518386679605--
------=_Part_8424_1246644764.1518386679604--
.
Author: Arthur O'Dwyer <arthur.j.odwyer@gmail.com>
Date: Sun, 11 Feb 2018 15:26:51 -0800 (PST)
Raw View
------=_Part_8519_1459136539.1518391611785
Content-Type: multipart/alternative;
boundary="----=_Part_8520_14006947.1518391611785"
------=_Part_8520_14006947.1518391611785
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
On Sunday, February 11, 2018 at 12:09:53 PM UTC-8, Alexander Zaitsev wrote:
>
> Hello,
>
> I want to get feedback about my proposal about adding prime test function=
s=20
> to C++. You can find it as an attached file.
>
> Open questions:
>
> - I am not sure about interface for is_probable_prime interface. On=20
> the one hand i don't want to see under the hood any specific=20
> imeplementation. On the other hand i should guarantee something (I mea=
n=20
> complexity and probablity).
>
>
> Do you have any suggestions?
>
Three comments of varying scope:
(1) I don't think Standard C++ has any need for these is_prime and=20
is_probable_prime functions. I would strongly discourage you from bringing=
=20
this paper forward with its current API, regardless of how much you tweak=
=20
the wording.
(2) The is_probable_prime() function's contract talks about returning true=
=20
if the number is "probably prime" with a certain "probability." This is=20
unlikely to be sensical. Each of the integers is either prime or non-prime;=
=20
there is no "probably" in this domain. If what you mean is that this=20
function performs a certain deterministic test for "probable-prime-hood=20
<https://en.wikipedia.org/wiki/Probable_prime>", then you must specify=20
*which* test it performs. Miller-Rabin? With how many factors? If you leave=
=20
it unspecified, different vendors might do different things, leading client=
=20
programs to have different behavior when compiled for different platforms.=
=20
Especially in cryptography, platform-dependent behavior is a reliability=20
nightmare.
(3) You should attempt to code up these two generic algorithms yourself.=
=20
Your API claims that your implementation is going to work for any=20
`Integral` type; is that concept actually sufficient to define primality,=
=20
let alone compute it? Prove it, by programming the algorithm yourself.=20
Include a reference implementation in your paper.
I suspect that you might find that even the simple `is_prime` API is not=20
sufficiently well-thought-out to be programmable in a generic-programming=
=20
style. (Take a look at all the trouble Stepanov had with "gcd"!) But I=20
look forward to being proven wrong by your efforts.
=E2=80=93Arthur
--=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/6053a44c-c1c3-4725-af3c-84092a0fdb4a%40isocpp.or=
g.
------=_Part_8520_14006947.1518391611785
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">On Sunday, February 11, 2018 at 12:09:53 PM UTC-8, Alexand=
er Zaitsev wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margi=
n-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"l=
tr">Hello,<div><br></div><div>I want to get feedback about my proposal abou=
t adding prime test functions to C++. You can find it as an attached file.<=
/div><div><br></div><div>Open questions:</div><div><ul><li>I am not sure ab=
out interface for is_probable_prime interface. On the one hand i don't =
want to see under the hood any specific imeplementation. On the other hand =
i should guarantee something (I mean complexity and probablity).</li></ul><=
/div><div><br></div><div>Do you have any suggestions?</div></div></blockquo=
te><div><br></div><div>Three comments of varying scope:</div><div>(1) =C2=
=A0I don't think Standard C++ has any need for these is_prime and is_pr=
obable_prime functions. I would strongly discourage you from bringing this =
paper forward with its current API, regardless of how much you tweak the wo=
rding.<br></div><div>(2) =C2=A0The is_probable_prime() function's contr=
act talks about returning true if the number is "probably prime" =
with a certain "probability." This is unlikely to be sensical. Ea=
ch of the integers is either prime or non-prime; there is no "probably=
" in this domain. If what you mean is that this function performs a ce=
rtain deterministic test for "<a href=3D"https://en.wikipedia.org/wiki=
/Probable_prime">probable-prime-hood</a>", then you must specify <i>wh=
ich</i> test it performs. Miller-Rabin? With how many factors? If you leave=
it unspecified, different vendors might do different things, leading clien=
t programs to have different behavior when compiled for different platforms=
.. Especially in cryptography, platform-dependent behavior is a reliability =
nightmare.</div><div>(3) =C2=A0You should attempt to code up these two gene=
ric algorithms yourself. Your API claims that your implementation is going =
to work for any `Integral` type; is that concept actually sufficient to def=
ine primality, let alone compute it? =C2=A0Prove it, by programming the alg=
orithm yourself. Include a reference implementation in your paper.</div><di=
v><br></div><div>I suspect that you might find that even the simple `is_pri=
me` API is not sufficiently well-thought-out to be programmable in a generi=
c-programming style. (Take a look at all the trouble Stepanov had with &quo=
t;gcd"!) =C2=A0But I look forward to being proven wrong by your effort=
s.</div><div><br></div><div>=E2=80=93Arthur</div></div>
<p></p>
-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/6053a44c-c1c3-4725-af3c-84092a0fdb4a%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/6053a44c-c1c3-4725-af3c-84092a0fdb4a=
%40isocpp.org</a>.<br />
------=_Part_8520_14006947.1518391611785--
------=_Part_8519_1459136539.1518391611785--
.
Author: Alexander Zaitsev <zamazan4ik@gmail.com>
Date: Sun, 11 Feb 2018 15:37:04 -0800 (PST)
Raw View
------=_Part_8538_309298163.1518392224305
Content-Type: multipart/alternative;
boundary="----=_Part_8539_679709398.1518392224305"
------=_Part_8539_679709398.1518392224305
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
=D0=BF=D0=BE=D0=BD=D0=B5=D0=B4=D0=B5=D0=BB=D1=8C=D0=BD=D0=B8=D0=BA, 12 =D1=
=84=D0=B5=D0=B2=D1=80=D0=B0=D0=BB=D1=8F 2018 =D0=B3., 2:26:51 UTC+3 =D0=BF=
=D0=BE=D0=BB=D1=8C=D0=B7=D0=BE=D0=B2=D0=B0=D1=82=D0=B5=D0=BB=D1=8C Arthur O=
'Dwyer=20
=D0=BD=D0=B0=D0=BF=D0=B8=D1=81=D0=B0=D0=BB:
>
> On Sunday, February 11, 2018 at 12:09:53 PM UTC-8, Alexander Zaitsev wrot=
e:
>>
>> Hello,
>>
>> I want to get feedback about my proposal about adding prime test=20
>> functions to C++. You can find it as an attached file.
>>
>> Open questions:
>>
>> - I am not sure about interface for is_probable_prime interface. On=
=20
>> the one hand i don't want to see under the hood any specific=20
>> imeplementation. On the other hand i should guarantee something (I me=
an=20
>> complexity and probablity).
>>
>>
>> Do you have any suggestions?
>>
>
> Three comments of varying scope:
> (1) I don't think Standard C++ has any need for these is_prime and=20
> is_probable_prime functions. I would strongly discourage you from bringin=
g=20
> this paper forward with its current API, regardless of how much you tweak=
=20
> the wording.
> (2) The is_probable_prime() function's contract talks about returning=20
> true if the number is "probably prime" with a certain "probability." This=
=20
> is unlikely to be sensical. Each of the integers is either prime or=20
> non-prime; there is no "probably" in this domain. If what you mean is tha=
t=20
> this function performs a certain deterministic test for "
> probable-prime-hood <https://en.wikipedia.org/wiki/Probable_prime>", then=
=20
> you must specify *which* test it performs. Miller-Rabin? With how many=20
> factors? If you leave it unspecified, different vendors might do differen=
t=20
> things, leading client programs to have different behavior when compiled=
=20
> for different platforms. Especially in cryptography, platform-dependent=
=20
> behavior is a reliability nightmare.
> (3) You should attempt to code up these two generic algorithms yourself.=
=20
> Your API claims that your implementation is going to work for any=20
> `Integral` type; is that concept actually sufficient to define primality,=
=20
> let alone compute it? Prove it, by programming the algorithm yourself.=
=20
> Include a reference implementation in your paper.
>
> I suspect that you might find that even the simple `is_prime` API is not=
=20
> sufficiently well-thought-out to be programmable in a generic-programming=
=20
> style. (Take a look at all the trouble Stepanov had with "gcd"!) But I=
=20
> look forward to being proven wrong by your efforts.
>
> =E2=80=93Arthur
>
1. Hah. I have another vision. Prime test function FMPOV are more useful=
=20
than Special Math Functions=20
(http://en.cppreference.com/w/cpp/numeric/special_math).
2. Yes, i agree with you. And now i am trying to find some good way for=
=20
avoiding problem with is_probable_prime function. I don't want to force=
=20
e.g. Miller-Rabin algorithm... But if it's only way - okay, i can do it.
3. Good point. I will add reference implementation to the paper.=20
=20
--=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/c21e25aa-b25b-47e3-a4d9-fd47f22c260d%40isocpp.or=
g.
------=_Part_8539_679709398.1518392224305
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><br><br>=D0=BF=D0=BE=D0=BD=D0=B5=D0=B4=D0=B5=D0=BB=D1=8C=
=D0=BD=D0=B8=D0=BA, 12 =D1=84=D0=B5=D0=B2=D1=80=D0=B0=D0=BB=D1=8F 2018 =D0=
=B3., 2:26:51 UTC+3 =D0=BF=D0=BE=D0=BB=D1=8C=D0=B7=D0=BE=D0=B2=D0=B0=D1=82=
=D0=B5=D0=BB=D1=8C Arthur O'Dwyer =D0=BD=D0=B0=D0=BF=D0=B8=D1=81=D0=B0=
=D0=BB:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.=
8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr">On Sun=
day, February 11, 2018 at 12:09:53 PM UTC-8, Alexander Zaitsev wrote:<block=
quote class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left=
:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr">Hello,<div><br></div><di=
v>I want to get feedback about my proposal about adding prime test function=
s to C++. You can find it as an attached file.</div><div><br></div><div>Ope=
n questions:</div><div><ul><li>I am not sure about interface for is_probabl=
e_prime interface. On the one hand i don't want to see under the hood a=
ny specific imeplementation. On the other hand i should guarantee something=
(I mean complexity and probablity).</li></ul></div><div><br></div><div>Do =
you have any suggestions?</div></div></blockquote><div><br></div><div>Three=
comments of varying scope:</div><div>(1) =C2=A0I don't think Standard =
C++ has any need for these is_prime and is_probable_prime functions. I woul=
d strongly discourage you from bringing this paper forward with its current=
API, regardless of how much you tweak the wording.<br></div><div>(2) =C2=
=A0The is_probable_prime() function's contract talks about returning tr=
ue if the number is "probably prime" with a certain "probabi=
lity." This is unlikely to be sensical. Each of the integers is either=
prime or non-prime; there is no "probably" in this domain. If wh=
at you mean is that this function performs a certain deterministic test for=
"<a href=3D"https://en.wikipedia.org/wiki/Probable_prime" target=3D"_=
blank" rel=3D"nofollow" onmousedown=3D"this.href=3D'https://www.google.=
com/url?q\x3dhttps%3A%2F%2Fen.wikipedia.org%2Fwiki%2FProbable_prime\x26sa\x=
3dD\x26sntz\x3d1\x26usg\x3dAFQjCNH6RhRV32Q-1px5wtyX4uzMR1dJ8A';return t=
rue;" onclick=3D"this.href=3D'https://www.google.com/url?q\x3dhttps%3A%=
2F%2Fen.wikipedia.org%2Fwiki%2FProbable_prime\x26sa\x3dD\x26sntz\x3d1\x26us=
g\x3dAFQjCNH6RhRV32Q-1px5wtyX4uzMR1dJ8A';return true;">probable-prime-h=
ood</a>", then you must specify <i>which</i> test it performs. Miller-=
Rabin? With how many factors? If you leave it unspecified, different vendor=
s might do different things, leading client programs to have different beha=
vior when compiled for different platforms. Especially in cryptography, pla=
tform-dependent behavior is a reliability nightmare.</div><div>(3) =C2=A0Yo=
u should attempt to code up these two generic algorithms yourself. Your API=
claims that your implementation is going to work for any `Integral` type; =
is that concept actually sufficient to define primality, let alone compute =
it? =C2=A0Prove it, by programming the algorithm yourself. Include a refere=
nce implementation in your paper.</div><div><br></div><div>I suspect that y=
ou might find that even the simple `is_prime` API is not sufficiently well-=
thought-out to be programmable in a generic-programming style. (Take a look=
at all the trouble Stepanov had with "gcd"!) =C2=A0But I look fo=
rward to being proven wrong by your efforts.</div><div><br></div><div>=E2=
=80=93Arthur</div></div></blockquote><div><br></div><div><ol><li>Hah. I hav=
e another vision. Prime test function FMPOV are more useful than Special Ma=
th Functions (http://en.cppreference.com/w/cpp/numeric/special_math).</li><=
li>Yes, i agree with you. And now i am trying to find some good way for avo=
iding problem with is_probable_prime function. I don't want to force e.=
g. Miller-Rabin algorithm... But if it's only way - okay, i can do it.<=
/li><li>Good point. I will add reference implementation to the paper.=C2=A0=
<br></li></ol></div></div>
<p></p>
-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/c21e25aa-b25b-47e3-a4d9-fd47f22c260d%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/c21e25aa-b25b-47e3-a4d9-fd47f22c260d=
%40isocpp.org</a>.<br />
------=_Part_8539_679709398.1518392224305--
------=_Part_8538_309298163.1518392224305--
.
Author: Thiago Macieira <thiago@macieira.org>
Date: Sun, 11 Feb 2018 22:28:36 -0800
Raw View
On domingo, 11 de fevereiro de 2018 14:04:39 PST Alexander Zaitsev wrote:
> =D0=B2=D0=BE=D1=81=D0=BA=D1=80=D0=B5=D1=81=D0=B5=D0=BD=D1=8C=D0=B5, 11 =
=D1=84=D0=B5=D0=B2=D1=80=D0=B0=D0=BB=D1=8F 2018 =D0=B3., 23:55:48 UTC+3 =D0=
=BF=D0=BE=D0=BB=D1=8C=D0=B7=D0=BE=D0=B2=D0=B0=D1=82=D0=B5=D0=BB=D1=8C Thiag=
o
> Macieira =D0=BD=D0=B0=D0=BF=D0=B8=D1=81=D0=B0=D0=BB:
> > Please add answers to these questions:
Please note I didn't ask you to answer in the mailing list. I asked you to =
add=20
this to the paper, as supporting evidence of why the committee should consi=
der=20
it.
> 1. Honestly, i don't know how I can measure frequency of using these
> functions. Depends on your domain. E.g. prime numbers are widely-used =
in
> cryptography. Also using prime numbers are required for some hash
> techniques.
That's the information you should talk about: what domains need this functi=
on?=20
Explain how those domains need to deploy the same function over and over=20
again.
This should also indicate which implementation you should recommend.
Note I also said *besides* cryptography.
> 2. About numbers wider than 64 bits - we have proposals about wide_int
> (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0539r2.html)=
.
> Also i am working on Unbounded integer. We can add interoperability wi=
th
> these types later.
I'm not asking for implementations wider than 64-bit. I was saying that=20
cryptography will need larger than 64-bit (much larger) and therefore won't=
be=20
using the standard library implementation anyway.
But this is a good point: of those other uses that you must surely know of,=
is=20
dealing with numbers larger than 64-bit a common occurrence?
> 4. Question about complexities is open. Because there are a
> lot of algorithms for prime check with different complexities. For is_pri=
me
> i added O(sqrt(N)), but there are faster algorithms. If we are talking
> about is_probable_prime, for now i am not sure which complexity should be
> chosen here. Do you have any ideas?
> 5. Should i suggest complete implementation or just names of possible
> algorithms?
See Arthur's reply about is_probable_prime.
For is_prime, I would list a simple implementation that runs in the complex=
ity=20
requirement, if it is of reasonable size to list in the paper. If it's not =
a=20
simple algorithm, then reference it by name.
--=20
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
--=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/2428464.Y3fiYV6T29%40tjmaciei-mobl1.
.