220 36873 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 14:04:39 -0800 (PST) Lines: 192 Approved: news@gmane.org Message-ID: References: <9150311.INAnE2rANT@tjmaciei-mobl1> Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_8424_1246644764.1518386679604" X-Trace: blaine.gmane.org 1518386578 21477 195.159.176.226 (11 Feb 2018 22:02:58 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sun, 11 Feb 2018 22:02:58 +0000 (UTC) To: ISO C++ Standard - Future Proposals Original-X-From: std-proposals+bncBDGLZGV44EEBB6H3QLKAKGQER4GUWOY@isocpp.org Sun Feb 11 23:02:54 2018 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-ua0-f200.google.com ([209.85.217.200]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ekzhk-0004EL-Bo for gclcip-std-proposals@m.gmane.org; Sun, 11 Feb 2018 23:02:36 +0100 Original-Received: by mail-ua0-f200.google.com with SMTP id p1sf9284874uab.15 for ; Sun, 11 Feb 2018 14:04:42 -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=Hy70tMGocM+v4C1KaeJGEFf/wtRfGbBnefQGN1SVhnw=; b=kJa4kZdEYm0OeAByBXMVoxEIfWyPpgIZit1x9/fV/vqemeuuYkty6UcB7OyBftafx9 131F42c1vLa2w1jF28rmOTjC2tBdovByBJqbPR4AvBs4Xx7KJ1g6pUi88L7yvb+CWpoa h9lJT1gXjfTj0laEQjNe660k7inWZ+2c5Owlwd7i/pv0K5zTZXnhSPlJVVhrbssdKh2Z hpJ9bgshqdzKUXq9G2Pxfz8+LyGpTE4rNjumfh5E80Rri4jZDBr2qQ7U0rLgN9zXOXLn O0co+iwqZo3e43/fetraIABUa+PHnulDKHkV/Qg29PmEJkN+QH0MVjzjVBrdrQvoidND GCig== 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=Hy70tMGocM+v4C1KaeJGEFf/wtRfGbBnefQGN1SVhnw=; b=W8+rJxXGu9pjaiI/peGbfvul5TniGngc+JismmugD4TF4+84Q01a/15ciweRbJvhmL jCmVUnAELROX7jK9ZolKVi7r5Wh5vysHv+VXfXizpMyBQsjbBbyzWInU/61xURgFL8CE V/JJrG6RgCLpo9CqrkXKdbmTDyS+NQAbdHFFN1Ur5wNgYSENEXfgdd9Xd36W8daFUw0n ACxNl2wyDM2M7v8zH3WXHzkAoX7ytqoFaJlcsF8G1cvk5v/9toiAtrbY/bcBRUgBFBjH w9LzSpgWf1qv72Lzk2jtRljiP9jjXT4dnX/HPiiXkF5DCCgeVnBd5gr5sUIXTkQSx9x6 V+ZA== 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=Hy70tMGocM+v4C1KaeJGEFf/wtRfGbBnefQGN1SVhnw=; b=EMOuwPnqhV1gT/Qd7zdbvPPTyTvvwkAMA8juXLrvXufqxjkxvC1G7QSRudCEE+c21r NdZ5nqIFEUi2EELvjZlAexjNc9BnzrXUS/KOJC1kqgLl3g48h4MukJhXChfudw+2uG6E 8PC8s9zsdzIegnLjvWySt4opYrlLBgn3QVmMO4llrQO71mD2ppCAQ5tmwPuspVB1Bgzl QKURkj6SX8TZNW+h3mkboBH+7ISbdnfDAZb7QgnpHbZV++EiNq+CSpYwc+4l4jk4N7/p Fm8aSlN7UYjzzGhVqP7tPma4yrqAGxNCS5CbwavawtbwwcEkbWZw81Zstewj/DS6zcyg nRuw== X-Gm-Message-State: APf1xPCDkWwmwPVzyq6zI8Y27HfiNrfrIzguUMGFZXZqOZIbczCd4f4I G/p5gYj5lUapXZBYEMJd18RRCw== X-Google-Smtp-Source: AH8x226y5fCDjMHSGMxFzZx6V0J9Dy1274kjk9x2nLUb4JopGEuQ1zF+9evGUpKcoR+P/Ng81zD+Og== X-Received: by 10.176.76.38 with SMTP id l38mr5666858uaf.80.1518386681824; Sun, 11 Feb 2018 14:04:41 -0800 (PST) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.31.92.199 with SMTP id q190ls6239617vkb.8.gmail; Sun, 11 Feb 2018 14:04:40 -0800 (PST) X-Received: by 10.31.50.209 with SMTP id y200mr866467vky.3.1518386680086; Sun, 11 Feb 2018 14:04:40 -0800 (PST) In-Reply-To: <9150311.INAnE2rANT@tjmaciei-mobl1> 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:36873 Archived-At: ------=_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


=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:
On Sunday, 11 February 201= 8 12:09:53 PST Alexander Zaitsev wrote:
> Hello,
>=20
> I want to get feedback about my proposal about adding prime test f= unctions
> to C++. You can find it as an attached file.
>=20
> Open questions:
>=20
> =C2=A0 =C2=A0- I am not sure about interface for is_probable_prime= interface. On the
> =C2=A0 =C2=A0one hand i don't want to see under the hood any s= pecific imeplementation.
> On the other hand i should guarantee something (I mean complexity = and
> probablity).
>=20
>=20
> Do you have any suggestions?

Please add answers to these questions:

How often is this necessary? What use-cases for it exist, besides crypt= ography=20
(which will need numbers wider than 64-bit anyway)? Does it even exist = in any=20
modern math library?

What is the complexity if this function? Do you have a suggested=20
implementation for it?

--=20
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
=C2=A0 =C2=A0Software Architect - Intel Open Source Technology Center




  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 number= s are required for some hash techniques.
  2. 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.
  3. Yes, i= t is. E.g.:=C2=A0https://gmplib.org/manual/Number-Theoretic-Functions.html = (mpz_probab_prime_p),=C2=A0https://docs.o= racle.com/javase/7/docs/api/java/math/BigInteger.html#isProbablePrime(int)<= /li>
  4. 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?
  5. Should i suggest complete implementation or j= ust names of possible algorithms?

--
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/d230ae55-fad0-4267-9ef2-cc861a0bfe41= %40isocpp.org.
------=_Part_8425_1218662995.1518386679605-- ------=_Part_8424_1246644764.1518386679604-- .