220 36875 <6053a44c-c1c3-4725-af3c-84092a0fdb4a@isocpp.org> article Path: news.gmane.org!.POSTED!not-for-mail From: Arthur O'Dwyer Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Prime test functions Date: Sun, 11 Feb 2018 15:26:51 -0800 (PST) Lines: 137 Approved: news@gmane.org Message-ID: <6053a44c-c1c3-4725-af3c-84092a0fdb4a@isocpp.org> References: Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_8519_1459136539.1518391611785" X-Trace: blaine.gmane.org 1518391523 32216 195.159.176.226 (11 Feb 2018 23:25:23 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sun, 11 Feb 2018 23:25:23 +0000 (UTC) To: ISO C++ Standard - Future Proposals Original-X-From: std-proposals+bncBDLZJYWNDQILZIUD2QCRUBDS3UHNU@isocpp.org Mon Feb 12 00:25:19 2018 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-vk0-f71.google.com ([209.85.213.71]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1el0zI-0006If-VW for gclcip-std-proposals@m.gmane.org; Mon, 12 Feb 2018 00:24:49 +0100 Original-Received: by mail-vk0-f71.google.com with SMTP id g66sf8232372vke.0 for ; Sun, 11 Feb 2018 15:26:54 -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=UCOf2ig5ULFLLLpfZ5qN+31H89U+FC7MW6n7vWOL67w=; b=G9LLkC4gjEKNaenyCTayViYcFbLgXBaPU4DOv9kWNlSE2B9bQ0P7296K6OmDEDwX8i Unqjk9QTAMHnbFklSMWzrIuLkc6AvBJ+PgHCoqypGamwl6lraPGlTumwjj2ixK3HKT2e 0q7wAweotAsuPd/TIWoqLYH4E0SDLKAiNFKh5hV9sbRpQoq0lgVEaf7Og9aVTxCKGXMD TUInhTQEIscOKoNo/SoOgYpy62LHGVULLwXbPHzj0DX1yVkaXlvsYji7W12Co6cb/K2Z 3hZwv1i826O8AWrWSYD4ZrkIrclPlTtRnwbjDAzFj6pydiC7LCW7czvT/iDYFBzqeWOm 833w== 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=UCOf2ig5ULFLLLpfZ5qN+31H89U+FC7MW6n7vWOL67w=; b=Cuu9W5nEvwMKBBuK8SMakAFSErWtsOh383tMpAK/9E4+mYjQoeqLlRyulkL5vJPJ4V 5FwmJ/QU6dtcCU/gPwGXIqIMP5EFkdwPhK9OpZeE77D/+5bn/vx+IF8uq3N3oYgffZ3W wHkiMb8yNSKMd+g8RDGQ5IK7NuYMMiznmUFHw94COPmMGLUnkatFmyrXgCJQLT17oS9a 4jMnFf3+yHVyJ2dbeMDVi7kNQoCjL6rtSQxzznatZgnlFXcpPr4TDLHKnjvSPsaivyS2 yKYUhEq0zPZVggMXSlRDQIz1DPo6lekYBUiQMvUCz8XJhZssAE5N8gR/GXnLq4GvOfd+ 6jPQ== 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=UCOf2ig5ULFLLLpfZ5qN+31H89U+FC7MW6n7vWOL67w=; b=ACCqvQ0x65Tv2HUufkyI/wqCEEBss1MwXiSk3MpNOAOHCCiOeZIvEMVdGD0QTSpUCk iSp/mfGgX+eJOsOfibo6vh2QW195nM9twRT2ePKT+V0tiDzAuitm6cf/5jpn95NfNtol SD9OtibHpKarG5Hg5hOkTpvkcz97/BxmFb2s6T1rDCI+AUCPB2Bsl2QEzytF18knFR8X xSyZj48bZ+jN3ZRrHNLDYjDKLX7H25/wis1l5rNTgA340sEjewjmoYdjCAr72AX1nyV6 tsCoFzVLz2FhJUu+P1UnKZ64ERHHgtl40hEcbJdWnPuqZdUByveg/50kREtDAiYAqYXn XScQ== X-Gm-Message-State: APf1xPDTbggI+ljbhNhqbUecqKrWvLNyR53Lw4fJBSOP0VdUrR7kmM1H iYQ4jZkY8S0lWArkwNViFxqGhQ== X-Google-Smtp-Source: AH8x226x/0A4J/IA3D0Bq8rLK7s2L6xk+qbJW7hxVqn44BRA1Ua+syj5Quz6GyWP81eijubi9qbhYA== X-Received: by 10.31.114.199 with SMTP id n190mr5243219vkc.3.1518391614267; Sun, 11 Feb 2018 15:26:54 -0800 (PST) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.31.238.73 with SMTP id m70ls6152606vkh.5.gmail; Sun, 11 Feb 2018 15:26:52 -0800 (PST) X-Received: by 10.31.169.23 with SMTP id s23mr876499vke.1.1518391612315; Sun, 11 Feb 2018 15:26:52 -0800 (PST) In-Reply-To: X-Original-Sender: arthur.j.odwyer@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:36875 Archived-At: ------=_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 ", 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
On Sunday, February 11, 2018 at 12:09:53 PM UTC-8, Alexand= er Zaitsev wrote:
Hello,

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>

Open questions:
  • 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).
<= /div>

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_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.
(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 "probable-prime-hood", then you must specify wh= ich 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.
(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.

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.

=E2=80=93Arthur

--
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/6053a44c-c1c3-4725-af3c-84092a0fdb4a= %40isocpp.org.
------=_Part_8520_14006947.1518391611785-- ------=_Part_8519_1459136539.1518391611785-- .