220 36876 article Path: news.gmane.org!.POSTED!not-for-mail From: Alexander Zaitsev Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Prime test functions Date: Sun, 11 Feb 2018 15:37:04 -0800 (PST) Lines: 183 Approved: news@gmane.org Message-ID: References: <6053a44c-c1c3-4725-af3c-84092a0fdb4a@isocpp.org> Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_8538_309298163.1518392224305" X-Trace: blaine.gmane.org 1518392119 9293 195.159.176.226 (11 Feb 2018 23:35:19 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sun, 11 Feb 2018 23:35:19 +0000 (UTC) To: ISO C++ Standard - Future Proposals Original-X-From: std-proposals+bncBDGLZGV44EEBBINHQPKAKGQEJK7K5BI@isocpp.org Mon Feb 12 00:35:14 2018 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-ua0-f198.google.com ([209.85.217.198]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1el19A-0001Fo-Q1 for gclcip-std-proposals@m.gmane.org; Mon, 12 Feb 2018 00:35:00 +0100 Original-Received: by mail-ua0-f198.google.com with SMTP id d21sf9422019ual.3 for ; Sun, 11 Feb 2018 15:37:06 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=isocpp-org.20150623.gappssmtp.com; s=20150623; h=date:from:to:message-id:in-reply-to:references:subject:mime-version :x-original-sender:reply-to:precedence:mailing-list:list-id :list-post:list-help:list-archive:list-subscribe:list-unsubscribe; bh=usK0Xn9tJQS8kDNKPgISS36LezeP3ZAapIpPyOIiC7I=; b=pgJGNXFsqifvJKzMAuJutYPXAEaNgjvdXRiZPmaSBrZBDSQAk2Fbtl2zvza3I7eKuT Go6UikBbQ2ivZGtjeVN/2kehf0aqNhnFyJmLkx6734TnlwgkQZdlzxsIyXb1SwdrT1c7 j90pLOvKs/Wrr5l3K9egrmWBVeWbDXkkaNBBkQXyxQZ2f6SgXP2/pTloFkmo9s27S41j ou6O812Bg41iwEb6skFaZnu7PWbCtHBArP9CRwzy7TNIdWynLQxRMWLvOEeZsIywAHOH PD3iyr4QYn6Enos0+gzYf034hYgz9zQkUhDzubri6IucNYBzR3F5UUhrjj7Ikp/Zu5T/ Jw/w== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:from:to:message-id:in-reply-to:references:subject:mime-version :x-original-sender:reply-to:precedence:mailing-list:list-id :list-post:list-help:list-archive:list-subscribe:list-unsubscribe; bh=usK0Xn9tJQS8kDNKPgISS36LezeP3ZAapIpPyOIiC7I=; b=dIdYy2ABXZSD+TzF8q6J32f0K6jwE9HAh+ay6wwvVHKaVI8UBmiK7YlTP2Dw7wTF0g swSan6t+vmDFgqgxuLAoO1I1AIvpizYmzAWrhJiYPq3Io0MnztxG9+xarmkAs5kK4GP5 bp2XeaowINVLlCp+6Q7r4VMhVAlapYShyEXIFeBMHB7I/3B7GE6alPm51Xm2x7tdHxKx fjvOnAQvBzCsT/kNx13g6sg+O9SPubrXXCpSNFk7SdiEnffoDvw04l2yg77HMmbWpv8p LIAOOXnr5CPQko2HfQIJGaMzZ3fzVh3x3VE/NHbdXk/OUJaoTvxQU2U50wymo0d0tcah U/+A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:message-id:in-reply-to:references :subject:mime-version:x-original-sender:reply-to:precedence :mailing-list:list-id:x-spam-checked-in-group:list-post:list-help :list-archive:list-subscribe:list-unsubscribe; bh=usK0Xn9tJQS8kDNKPgISS36LezeP3ZAapIpPyOIiC7I=; b=UWIiIk7ybAP+0FvtfeA3hUiUnnrAKTb8Xf18VPNJ26W+DRg4b8rG845BYaIud3IO7e mJXjtkn5WfQ1CCkwtmNvBAMMNCdO65jUae4qy76FZMxVZL321uZUcoFuaZMOBzdz/Nlo URmtAnYtI4p+D1fyWwmDyejIKj4VRNm6Cd6vi8TElDIckMCa4CmB/ABYXHOaI4APQiow tTSSZ/b31kWseedbg1sfcKbCIHbQJmrcnd2zWAnX8QZFDmm68b44Eeb6NMBfV5B2NveH fu9L5S/Jflr2lH3JGAghahqw+/2dZXVlodHoL42f9vtb8Y645/E2YmLnC+7D/renwYvA guSg== X-Gm-Message-State: APf1xPCGv+Y0k2sZE1fN+9omI3XO9VFhFKsU9Ne/K8UltBqgQBOPRcub bekByX/B6gGckRBroJKlDYXRAA== X-Google-Smtp-Source: AH8x225Q+5bmIaBl0HP+nuBi8bRaNepEpgiakm6vknu66VcPwPhpd/coOpzS/Ox9x6Kizqn+7osc0Q== X-Received: by 10.176.48.87 with SMTP id x23mr5665531ual.4.1518392226389; Sun, 11 Feb 2018 15:37:06 -0800 (PST) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.31.169.142 with SMTP id s136ls6961660vke.18.gmail; Sun, 11 Feb 2018 15:37:04 -0800 (PST) X-Received: by 10.31.136.139 with SMTP id k133mr880868vkd.8.1518392224765; Sun, 11 Feb 2018 15:37:04 -0800 (PST) In-Reply-To: <6053a44c-c1c3-4725-af3c-84092a0fdb4a@isocpp.org> X-Original-Sender: zamazan4ik@gmail.com Precedence: list Mailing-list: list std-proposals@isocpp.org; contact std-proposals+owners@isocpp.org List-ID: X-Spam-Checked-In-Group: std-proposals@isocpp.org X-Google-Group-Id: 399137483710 List-Post: , List-Help: , List-Archive: List-Subscribe: , List-Unsubscribe: , Xref: news.gmane.org gmane.comp.lang.c++.isocpp.proposals:36876 Archived-At: ------=_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 ", 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


=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:
On Sun= day, 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 to C++. You can find it as an attached file.

Ope= n questions:
  • 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).

Do = you have any suggestions?

Three= comments of varying scope:
(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.
(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= "probable-prime-h= ood", then you must specify which 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.
(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.

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.

=E2= =80=93Arthur

  1. 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).
    2. <= 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>
  2. Good point. I will add reference implementation to the paper.=C2=A0=

--
You received this message because you are subscribed to the Google Groups &= quot;ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to std-proposa= ls+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.org.
------=_Part_8539_679709398.1518392224305-- ------=_Part_8538_309298163.1518392224305-- .