Can you run:

debuginfo-install rdesktop

and then recreate to collect a more detail backtrace?  Also:

RDESKTOP_DEBUG=Protocol rdesktop -v <server>

might give some more info.

What OS is the remote server running?

The remote host is Windows Server 2012 R2.

RDESKTOP_DEBUG=Protocol prints the following output:

Autoselecting keyboard map 'en-us' from locale
is_wm_active(): WM name: Sawf
Protocol(debug): rdp_reset_state()
Protocol(debug): mcs_connect_start()
Connecting to server using NLA...
Protocol(warning): Protocol negotiation failed with reason: SSL not allowed by server
Retrying with plain RDP.
Protocol(debug): sec_out_mcs_connect_initial_pdu()
Protocol(debug): sec_out_mcs_data(), g_num_channels is 5
Protocol(debug): sec_out_mcs_data(), requesting channel cliprdr
Protocol(debug): sec_out_mcs_data(), requesting channel rdpsnd
Protocol(debug): sec_out_mcs_data(), requesting channel snddbg
Protocol(debug): sec_out_mcs_data(), requesting channel rdpdr
Protocol(debug): sec_out_mcs_data(), requesting channel drdynvc
Protocol(debug): mcs_connect_finalize()
Protocol(debug): mcs_send_connect_initial()
Protocol(debug): mcs_recv_connect_response()
Protocol(debug): sec_process_mcs_data()
Protocol(debug): sec_process_mcs_data(), SEC_TAG_SRV_INFO
Protocol(debug): sec_process_srv_info(), server RDP version is 4
Protocol(debug): sec_process_mcs_data(), SEC_TAG_SRV_CHANNELS
Protocol(debug): sec_process_mcs_data(), SEC_TAG_SRV_CRYPT
Protocol(debug): sec_process_crypt_info()
Protocol(debug): sec_parse_crypt_info()
Protocol(debug): sec_parse_crypt_info(), We're going for the RDP5-style encryption
Protocol(debug): sec_parse_crypt_info(), server CA Certificate length is 1010
Protocol(debug): sec_parse_crypt_info(), certificate length is 1046
Segmentation fault (core dumped)

The backtrace:

Protocol(debug): sec_parse_crypt_info(), certificate length is 1046

Program received signal SIGSEGV, Segmentation fault.
0x00007ffff7f199c7 in __gmpz_sizeinbase (x=x@entry=0x7fffffffcf4c, base=base@entry=2) at mpz/sizeinbase.c:40
Downloading 0.00 MB source file /usr/src/debug/gmp-6.2.0-7.fc35.x86_64/mpz/sizeinbase.c
40	  MPN_SIZEINBASE (result, PTR(x), ABSIZ(x), base);
Missing separate debuginfos, use: dnf debuginfo-install krb5-libs-1.19.2-2.fc35.x86_64
(gdb) where
#0  0x00007ffff7f199c7 in __gmpz_sizeinbase (x=x@entry=0x7fffffffcf4c, 
    base=base@entry=2) at mpz/sizeinbase.c:40
#1  0x00005555555807d9 in rdssl_rkey_get_exp_mod (max_exp_len=4, 
    max_mod_len=256, modulus=0x7fffffffcfb0 "", exponent=0x7fffffffcf4c "", 
    rkey=0x555555988620)
    at /usr/src/debug/rdesktop-1.9.0-6.fc35.x86_64/ssl.c:313
#2  sec_parse_crypt_info (exponent=0x7fffffffcf4c "", 
    modulus=0x7fffffffcfb0 "", server_random=<synthetic pointer>, 
    rc4_key_size=<synthetic pointer>, s=0x5555555d89a0 <g_in.lto_priv>)
    at /usr/src/debug/rdesktop-1.9.0-6.fc35.x86_64/secure.c:762
#3  sec_process_crypt_info (s=0x5555555d89a0 <g_in.lto_priv>)
    at /usr/src/debug/rdesktop-1.9.0-6.fc35.x86_64/secure.c:789
#4  sec_process_mcs_data (s=0x5555555d89a0 <g_in.lto_priv>)
    at /usr/src/debug/rdesktop-1.9.0-6.fc35.x86_64/secure.c:848
#5  mcs_recv_connect_response (mcs_data=<optimized out>)
    at /usr/src/debug/rdesktop-1.9.0-6.fc35.x86_64/mcs.c:134
#6  mcs_connect_finalize (mcs_data=<optimized out>)
    at /usr/src/debug/rdesktop-1.9.0-6.fc35.x86_64/mcs.c:382
#7  0x0000555555567644 in sec_connect (reconnect=<optimized out>, 
    password=0x5555555f6de0 <g_password> "", domain=0x7fffffffdc60 "", 
    username=<optimized out>, server=0x7fffffffdd60 "ate")
    at /usr/src/debug/rdesktop-1.9.0-6.fc35.x86_64/secure.c:1020
#8  rdp_connect (password=0x5555555f6de0 <g_password> "", 
--Type <RET> for more, q to quit, c to continue without paging--c
    reconnect=<optimized out>, directory=0x7fffffffda60 "", command=0x7fffffffdb60 "", domain=0x7fffffffdc60 "", flags=307, server=0x7fffffffdd60 "ate") at /usr/src/debug/rdesktop-1.9.0-6.fc35.x86_64/rdp.c:2107
#9  main (argc=<optimized out>, argv=<optimized out>) at /usr/src/debug/rdesktop-1.9.0-6.fc35.x86_64/rdesktop.c:1374

In dmesg ouptut there is the following line:

[771902.200042] traps: rdesktop[292680] general protection fault ip:7fb8bdaf49c7 sp:7ffc64422758 error:0 in libgmp.so.10.4.0[7fb8bdae3000+78000]

I tried also remmina and xfreerdp, and both are able to connect to the same terminal server.

I was not able to reproduce this on F36:

rdesktop-1.9.0-7.fc36.x86_64

This version of rdesktop does not crash on me anymore. So maybe backport it to F35 as well?

There is do difference in the rdesktop package between F36 and F35.

Interesting. I am trying this against the same Windows server, but it might be updated in the meantime. Or it can be some library used by rdesktop (gmp?).

on fc35:

dnf --releasever=36 download --source rdesktop
rpmbuild --rebuild rdesktop-1.9.0-8.fc36.src.rpm
dnf install ~/rpmbuild/RPMS/x86_64/rdesktop-1.9.0-8.fc35.x86_64.rpm

but still

Protocol(warning): Protocol negotiation failed with reason: SSL not allowed by server
Retrying with plain RDP.
Segmentation fault (core dumped)

so I presume the problem is with some libraries on fc35:

dnf distrosync rdesktop
ldd /bin/rdesktop
        linux-vdso.so.1 (0x00007ffdb5b9a000)
        libgmp.so.10 => /lib64/libgmp.so.10 (0x00007f2b6732e000)
        libgssapi_krb5.so.2 => /lib64/libgssapi_krb5.so.2 (0x00007f2b672d7000)
        libXrandr.so.2 => /lib64/libXrandr.so.2 (0x00007f2b672ca000)
        libXcursor.so.1 => /lib64/libXcursor.so.1 (0x00007f2b672bd000)
        libtasn1.so.6 => /lib64/libtasn1.so.6 (0x00007f2b672a5000)
        libnettle.so.8 => /lib64/libnettle.so.8 (0x00007f2b67250000)
        libhogweed.so.6 => /lib64/libhogweed.so.6 (0x00007f2b6720d000)
        libgnutls.so.30 => /lib64/libgnutls.so.30 (0x00007f2b66ff1000)
        libpcsclite.so.1 => /lib64/libpcsclite.so.1 (0x00007f2b66fe4000)
        libpulse.so.0 => /lib64/libpulse.so.0 (0x00007f2b66f8e000)
        libX11.so.6 => /lib64/libX11.so.6 (0x00007f2b66e46000)
        libc.so.6 => /lib64/libc.so.6 (0x00007f2b66c3b000)
        libkrb5.so.3 => /lib64/libkrb5.so.3 (0x00007f2b66b5d000)
        libk5crypto.so.3 => /lib64/libk5crypto.so.3 (0x00007f2b66b45000)
        libcom_err.so.2 => /lib64/libcom_err.so.2 (0x00007f2b66b3e000)
        libkrb5support.so.0 => /lib64/libkrb5support.so.0 (0x00007f2b66b2d000)
        libkeyutils.so.1 => /lib64/libkeyutils.so.1 (0x00007f2b66b26000)
        libcrypto.so.1.1 => /lib64/libcrypto.so.1.1 (0x00007f2b66836000)
        libresolv.so.2 => /lib64/libresolv.so.2 (0x00007f2b66822000)
        libXext.so.6 => /lib64/libXext.so.6 (0x00007f2b6680d000)
        libXrender.so.1 => /lib64/libXrender.so.1 (0x00007f2b66800000)
        libXfixes.so.3 => /lib64/libXfixes.so.3 (0x00007f2b667f7000)
        libz.so.1 => /lib64/libz.so.1 (0x00007f2b667dd000)
        libp11-kit.so.0 => /lib64/libp11-kit.so.0 (0x00007f2b666a9000)
        libidn2.so.0 => /lib64/libidn2.so.0 (0x00007f2b66659000)
        libunistring.so.2 => /lib64/libunistring.so.2 (0x00007f2b664d4000)
        /lib64/ld-linux-x86-64.so.2 (0x00007f2b677a8000)
        libpulsecommon-15.0.so => /usr/lib64/pulseaudio/libpulsecommon-15.0.so (0x00007f2b66447000)
        libm.so.6 => /lib64/libm.so.6 (0x00007f2b6636b000)
        libdbus-1.so.3 => /lib64/libdbus-1.so.3 (0x00007f2b66317000)
        libxcb.so.1 => /lib64/libxcb.so.1 (0x00007f2b662ec000)
        libselinux.so.1 => /lib64/libselinux.so.1 (0x00007f2b662c1000)
        libffi.so.6 => /lib64/libffi.so.6 (0x00007f2b662b6000)
        libsndfile.so.1 => /lib64/libsndfile.so.1 (0x00007f2b6623f000)
        libsystemd.so.0 => /lib64/libsystemd.so.0 (0x00007f2b6616d000)
        libasyncns.so.0 => /lib64/libasyncns.so.0 (0x00007f2b66163000)
        libXau.so.6 => /lib64/libXau.so.6 (0x00007f2b6615d000)
        libpcre2-8.so.0 => /lib64/libpcre2-8.so.0 (0x00007f2b660c1000)
        libgsm.so.1 => /lib64/libgsm.so.1 (0x00007f2b660b2000)
        libFLAC.so.8 => /lib64/libFLAC.so.8 (0x00007f2b66057000)
        libvorbis.so.0 => /lib64/libvorbis.so.0 (0x00007f2b66028000)
        libvorbisenc.so.2 => /lib64/libvorbisenc.so.2 (0x00007f2b65f7b000)
        libopus.so.0 => /lib64/libopus.so.0 (0x00007f2b65f21000)
        libogg.so.0 => /lib64/libogg.so.0 (0x00007f2b65f16000)
        liblzma.so.5 => /lib64/liblzma.so.5 (0x00007f2b65eea000)
        libzstd.so.1 => /lib64/libzstd.so.1 (0x00007f2b65e3b000)
        liblz4.so.1 => /lib64/liblz4.so.1 (0x00007f2b65e17000)
        libcap.so.2 => /lib64/libcap.so.2 (0x00007f2b65e0b000)
        libgcrypt.so.20 => /lib64/libgcrypt.so.20 (0x00007f2b65ccf000)
        libgcc_s.so.1 => /lib64/libgcc_s.so.1 (0x00007f2b65cb4000)
        libgpg-error.so.0 => /lib64/libgpg-error.so.0 (0x00007f2b65c8e000)

This message is a reminder that Fedora Linux 35 is nearing its end of life.
Fedora will stop maintaining and issuing updates for Fedora Linux 35 on 2022-12-13.
It is Fedora's policy to close all bug reports from releases that are no longer
maintained. At that time this bug will be closed as EOL if it remains open with a
'version' of '35'.

Package Maintainer: If you wish for this bug to remain open because you
plan to fix it in a currently maintained version, change the 'version' 
to a later Fedora Linux version.

Thank you for reporting this issue and we are sorry that we were not 
able to fix it before Fedora Linux 35 is end of life. If you would still like 
to see this bug fixed and are able to reproduce it against a later version 
of Fedora Linux, you are encouraged to change the 'version' to a later version
prior to this bug being closed.

Fedora Linux 35 entered end-of-life (EOL) status on 2022-12-13.

Fedora Linux 35 is no longer maintained, which means that it
will not receive any further security or bug fix updates. As a result we
are closing this bug.

If you can reproduce this bug against a currently maintained version of Fedora Linux
please feel free to reopen this bug against that version. Note that the version
field may be hidden. Click the "Show advanced fields" button if you do not see
the version field.

If you are unable to reopen this bug, please file a new report against an
active release.

Thank you for reporting this bug and we are sorry it could not be fixed.